题号放这里自己去找吧。
HDU-2566
这题最开始用的dp，然后，被同学用奇思妙想过了。 >_< 开心！
-_- !! 然后，被我线性代数给过了。
方法一：dp
将其化为01背包，只不过每种物品可以重复取的各数和为n就行。
好了，代码如下：
#include<iostream>
#include<cstring>
using namespace std;
int dp[][];
int w[]={,,,};
int main()
{
int k, n, v;
cin>>k;
while(k--)
{
memset(dp, ,sizeof(dp));
cin>>n>>v;
dp[][]=;
for(int i=;i<=;i++)
{
for(int k=;k<=n;k++)
for(int j=w[i]; j<=v;j++)
dp[k][j]+=dp[k-][j-w[i]];
}
cout<<dp[n][v]<<endl;
}
}
哎呀，背包都差不多忘了。得复习了。
方法二：
因为 2 2 2 2 可以转化为 1 1 1 5啊；也就是说找最多的2的方案，当然余出来的1是不可组的。当然，最多2的情况来转化1115的情况
#include<cstdio>
int main(){
int T;
scanf("%d",&T);
while(T--){
int n, m;
int a=,b=,c=;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
for(int j=;j+i<=n;j++){
if(j*+i+(n-j-i)* == m){
b = j;
i = n;
break;
}
}
}
printf("%d\n",+b/);
}
return ;
}
感觉这个方法，我也不是很清楚。可能没说明白。
方法三：
设a ， b， c分别是1元 2元 5元的个数，那么也就是a+b+c=n和a+2*b+5*c=m这样就构成了一个矩阵方程。直接解开这个矩阵方程就行啦。
当然，还有更加明白的解释方法。一只3个未知数和两个约数条件，那么我们可以利用高中学过的消元，用一个未知数表示其他两个未知数。
即得到b = -4 * c + m - n;
a = 3 * c+ 2 * n - m;这两个公式，然后直接枚举c就可以了，注意的是，a+b+c=n一定是成立的。但是，由于数学公式要满足实际问题的需要
我们只能取a， b大于等于0的情况。
#include<cstdio> int main()
{
int t;
scanf("%d", &t);
while (t--)
{
int n, m;
scanf("%d%d", &n, &m);
int a, b, c = ;
int ans = ;
while ()
{
b = - * c + m - n;
a = * c+ * n - m;
if (b>=&&a>=)ans++;
else if (b < ) break;
c++;
}
printf("%d\n", ans);
}
return ;
}