https://vjudge.net/problem/HDU-1398
#include <cstdio>
using namespace std;
const int maxn= 310;
// c1是保存各项质量砝码可以组合的数目
// c2是中间量，保存每一次的情况
int c1[maxn], c2[maxn],step[20];
int main()
{ int n;
for(int i=0;i<=17;i++)
step[i]=i*i;
while(scanf("%d",&n)!=EOF,n)
{
for(int i=0;i<=n;i++)
{
c1[i]=1;
c2[i]=0;
}
for(int i=2;i*i<=n;i++)
{
for(int j=0;j<=n;j++)
{
for(int k=0;k+j<=n;k+=step[i])
{
c2[j+k]+=c1[j];
}
}
for(int j=0;j<=n;j++)
{
c1[j]=c2[j];
c2[j]=0;
}
}
printf("%d\n",c1[n]);
}
return 0;
}
https://vjudge.net/problem/HDU-1085
题意： 给你a个一元硬币，b个两元硬币，c个五元硬币，问不能凑出来的最小面额是多少。
#include <cstdio>
#include<string.h>
using namespace std;
const int maxn= 8010;
// c1是保存各项质量砝码可以组合的数目
// c2是中间量，保存每一次的情况
int c1[maxn], c2[maxn],step[5]={0,1,2,5};
int main()
{
int a,b,c;
while(scanf("%d%d%d",&a,&b,&c)!=EOF,a+b+c)
{
memset(c1,0,sizeof(c1));
memset(c2,0,sizeof(c2));
for(int i=0;i<=a;i++)
{
c1[i]=1;
}
for(int j=0;j<=a;j++)
{
for(int k=0;k<=b*2;k+=step[2])
{
c2[j+k]+=c1[j];
}
}
for(int i=0;i<=a+b*2;i++)
{
c1[i]=c2[i];
c2[i]=0;
}
for(int j=0;j<=a+b*2;j++)
{
for(int k=0;k<=c*5;k+=step[3])
{
c2[j+k]+=c1[j];
}
}
for(int i=0;i<=a+b*2+c*5;i++)
{
c1[i]=c2[i];
c2[i]=0;
}
int j;
for(j=0;j<=a+b*2+c*5;j++)
{
if(c1[j]==0) {
printf("%d\n",j);
break;
}
}
if(j==a+b*2+c*5+1) printf("%d\n",j);
}
return 0;
}
https://vjudge.net/problem/HDU-1171
题意：有n样物品，每样物品价值是val[ i ]，件数是num[ i ]。尽量把这些物品分成两堆使得两边总价值最接近。输出分得的两堆各自的价值,价值大的在前面。
题解：假设物品i的价值为v，数量为n；则该物品的母函数为(1+xv+x2v+...+x(n-1)v+xnv)
#include <cstdio>
#include<string.h>
using namespace std;
const int maxn= 255555;
int c1[maxn], c2[maxn],val[55],num[55];
int main()
{
int n;
while(scanf("%d",&n)!=EOF&&n>0)
{
memset(c1,0,sizeof(c1));
memset(c2,0,sizeof(c2));
int total=0;
for(int i=1;i<=n;i++) {
scanf("%d%d",val+i,num+i);
total+=val[i]*num[i];
}
for(int i=0;i<=num[1];i++)
c1[i*val[1]]=1;
int curr=num[1]*val[1];
for(int i=2;i<=n;i++)
{
for(int j=0;j<=curr;j++)
{
for(int k=0;k<=num[i];k++)
{
c2[j+k*val[i]]+=c1[j];
}
}
curr+=num[i]*val[i];
for(int j=0;j<=curr;j++)
{
c1[j]=c2[j];
c2[j]=0;
}
}
int j;
for(j=total/2;j>=0;j--)
{
if(c1[j]) break;
}
printf("%d %d\n",total-j, j);
}
return 0;
}
https://vjudge.net/problem/HDU-1709
题意：有一个天平，有n个砝码，重量分别为wi，求出所有不能用天平测量的重量。
题解：每个砝码可以不用，也可以放左边或者放右边。
#include <cstdio>
#include<string.h>
using namespace std;
const int maxn= 22222;
int c1[maxn], c2[maxn],val[55],ans[maxn];
const int shift=10001;
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
memset(c1,0,sizeof(c1));
memset(c2,0,sizeof(c2));
for(int i=1;i<=n;i++)
scanf("%d",val+i);
for(int i=-1;i<=1;i++)
c1[i*val[1]+shift]=1;
int curr=val[1]+shift,num=0,lef=shift-val[1];
for(int i=2;i<=n;i++)
{
for(int j=lef;j<=curr;j++)
{
for(int k=-1;k<=1;k++)
{
c2[j+k*val[i]]+=c1[j];
}
}
curr+=val[i];
lef-=val[i];
for(int j=lef;j<=curr;j++)
{
c1[j]=c2[j];
c2[j]=0;
}
}
for(int i=lef;i<=curr;i++)
{
if(c1[i]==0&&i-shift>0)
{
ans[num++]=i-shift;
}
}
printf("%d\n",num);
if(num!=0) printf("%d",ans[0]);
for(int i=1;i<num;i++)
{
printf(" %d",ans[i]);
}
if(num!=0) printf("\n");
}
return 0;
}
https://vjudge.net/problem/HDU-2069
题意：现在有价值为n的硬币，然后你有1,5,10,25,50的小硬币。有多少种方法凑成价值为n的硬币。注意：最多只能使用100个硬币。
题解：与一般母函数不同，一般的母函数是控制每种硬币的数量，或者是不控制，而此题控制的总的金币数目不能超过100，所以开一个二维数组来控制总的硬币的数目。
#include <cstdio>
#include<string.h>
using namespace std;
const int maxn= 260;
int c1[maxn][110], c2[maxn][110];//第一维是系数，第二维是硬币总数
int c3[maxn],val[6]={0,1,5,10,25,50};
int main()
{
int n;
memset(c1,0,sizeof(c1));
memset(c2,0,sizeof(c2));
for(int i=0;i<=100;i+=val[1])
{
c1[i][i]=1;
}
for(int i=2;i<=5;i++)
{
for(int j=0;j<=250;j++)
{
for(int k=0;j+k<=250;k+=val[i])
{
for(int p=0;p+k/val[i]<=100;p++)
{
c2[j+k][p+k/val[i]]+=c1[j][p];//控制金币总数不超过100
}
}
}
for(int j=0;j<=250;j++)
{
for(int p=0;p<=100;p++)
{
c1[j][p]=c2[j][p];
c2[j][p]=0;
}
}
}
memset(c3,0,sizeof(c3));
for(int i=0;i<=250;i++)
{
for(int j=0;j<=100;j++)
{
c3[i]+=c1[i][j];
}
}
while(scanf("%d",&n)!=EOF)
{
if(n<0) printf("0\n");
else printf("%d\n",c3[n]);
}
return 0;
}
https://vjudge.net/problem/HDU-2152
#include<cstdio>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn=110;
int c1[maxn],c2[maxn];
int lef[maxn],rig[maxn];
//把每种水果的价钱设置为1；则买m个水果相当于买m元水果。
//或者这样理解：买m个水果，水果的个数就为母函数的指数，个数的增值的步长每次都是1
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=1;i<=n;i++)
{
scanf("%d%d",lef+i,rig+i);
}
memset(c1,0,sizeof(c1));
memset(c2,0,sizeof(c2));
for(int i=lef[1];i<=m&&i<=rig[1];i++)
{
c1[i]=1;
}
int st=min(lef[1],m),ed=min(rig[1],m);
for(int i=2;i<=n;i++)
{
for(int j=st;j<=ed;j++)
{
for(int k=lef[i];k<=rig[i];k++)
{
if(j+k<=m){
c2[j+k]+=c1[j];
}
else break;
}
}
st=min(st+lef[i],m);
ed=min(ed+rig[i],m);
for(int j=st;j<=ed;j++)
{
c1[j]=c2[j];
c2[j]=0;
}
}
printf("%d\n",c1[m]);
}
return 0;
}
https://vjudge.net/problem/HDU-2082
题意：假设有x1个字母A， x2个字母B,..... x26个字母Z，同时假设字母A的价值为1，字母B的价值为2,..... 字母Z的价值为26。那么，对于给定的字母，可以找到多少价值<=50的单词呢？单词的价值就是组成一个单词的所有字母的价值之和，比如，单词ACM的价值是1+3+14=18，单词HDU的价值是8+4+21=33。(组成的单词与排列顺序无关，比如ACM与CMA认为是同一个单词）。
#include <cstdio>
#include<string.h>
using namespace std;
const int maxn=55;
long long c1[maxn],c2[maxn];
int num[30];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
for(int i=1;i<=26;i++)
{
scanf("%lld",num+i);
}
memset(c1,0,sizeof(c1));
memset(c2,0,sizeof(c2));
for(int i=0;i<=num[1];i++){
c1[i]=1;
}
for(int i=2;i<=26;i++)
{
for(int j=0;j<=50;j++)
{
for(int k=0;j+k*i<=50&&k<=num[i];k++)
{
c2[j+k*i]+=c1[j];
}
}
for(int j=0;j<=50;j++)
{
c1[j]=c2[j];
c2[j]=0;
}
}
long long sum=0;
for(int i=1;i<=50;i++)
sum+=c1[i];
printf("%lld\n",sum);
}
return 0;
}
