https://vjudge.net/problem/HDU-1398
#include <cstdio>
using namespace std;
const int maxn= 310;
// c1是保存各項(xiàng)質(zhì)量砝碼可以組合的數(shù)目
// 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個(gè)一元硬幣，b個(gè)兩元硬幣，c個(gè)五元硬幣，問(wèn)不能湊出來(lái)的最小面額是多少。
#include <cstdio>
#include<string.h>
using namespace std;
const int maxn= 8010;
// c1是保存各項(xiàng)質(zhì)量砝碼可以組合的數(shù)目
// 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樣物品，每樣物品價(jià)值是val[ i ]，件數(shù)是num[ i ]。盡量把這些物品分成兩堆使得兩邊總價(jià)值最接近。輸出分得的兩堆各自的價(jià)值,價(jià)值大的在前面。
題解：假設(shè)物品i的價(jià)值為v，數(shù)量為n；則該物品的母函數(shù)為(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
題意：有一個(gè)天平，有n個(gè)砝碼，重量分別為wi，求出所有不能用天平測(cè)量的重量。
題解：每個(gè)砝碼可以不用，也可以放左邊或者放右邊。
#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
題意：現(xiàn)在有價(jià)值為n的硬幣，然后你有1,5,10,25,50的小硬幣。有多少種方法湊成價(jià)值為n的硬幣。注意：最多只能使用100個(gè)硬幣。
題解：與一般母函數(shù)不同，一般的母函數(shù)是控制每種硬幣的數(shù)量，或者是不控制，而此題控制的總的金幣數(shù)目不能超過(guò)100，所以開(kāi)一個(gè)二維數(shù)組來(lái)控制總的硬幣的數(shù)目。
#include <cstdio>
#include<string.h>
using namespace std;
const int maxn= 260;
int c1[maxn][110], c2[maxn][110];//第一維是系數(shù)，第二維是硬幣總數(shù)
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];//控制金幣總數(shù)不超過(guò)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];
//把每種水果的價(jià)錢(qián)設(shè)置為1；則買m個(gè)水果相當(dāng)于買m元水果。
//或者這樣理解：買m個(gè)水果，水果的個(gè)數(shù)就為母函數(shù)的指數(shù)，個(gè)數(shù)的增值的步長(zhǎng)每次都是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
題意：假設(shè)有x1個(gè)字母A， x2個(gè)字母B,..... x26個(gè)字母Z，同時(shí)假設(shè)字母A的價(jià)值為1，字母B的價(jià)值為2,..... 字母Z的價(jià)值為26。那么，對(duì)于給定的字母，可以找到多少價(jià)值<=50的單詞呢？單詞的價(jià)值就是組成一個(gè)單詞的所有字母的價(jià)值之和，比如，單詞ACM的價(jià)值是1+3+14=18，單詞HDU的價(jià)值是8+4+21=33。(組成的單詞與排列順序無(wú)關(guān)，比如ACM與CMA認(rèn)為是同一個(gè)單詞）。
#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;
}
