https://vjudge.net/problem/HDU-1398
#include <cstdio>
using namespace std;
const int maxn= 310;
// c1是保存各項質(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個一元硬幣姆蘸，b個兩元硬幣昌渤，c個五元硬幣能岩，問不能湊出來的最小面額是多少沥阱。
#include <cstdio>
#include<string.h>
using namespace std;
const int maxn= 8010;
// c1是保存各項質(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樣物品更卒，每樣物品價值是val[ i ]等孵，件數(shù)是num[ i ]。盡量把這些物品分成兩堆使得兩邊總價值最接近逞壁。輸出分得的兩堆各自的價值,價值大的在前面流济。
題解：假設(shè)物品i的價值為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
題意：有一個天平绳瘟，有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
題意：現(xiàn)在有價值為n的硬幣蘸泻，然后你有1,5,10,25,50的小硬幣琉苇。有多少種方法湊成價值為n的硬幣。注意：最多只能使用100個硬幣悦施。
題解：與一般母函數(shù)不同并扇，一般的母函數(shù)是控制每種硬幣的數(shù)量，或者是不控制抡诞，而此題控制的總的金幣數(shù)目不能超過100穷蛹，所以開一個二維數(shù)組來控制總的硬幣的數(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ù)不超過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];
//把每種水果的價錢設(shè)置為1肴熏；則買m個水果相當于買m元水果。
//或者這樣理解：買m個水果顷窒，水果的個數(shù)就為母函數(shù)的指數(shù)蛙吏，個數(shù)的增值的步長每次都是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個字母A， x2個字母B,..... x26個字母Z鞋吉，同時假設(shè)字母A的價值為1鸦做，字母B的價值為2,..... 字母Z的價值為26。那么坯辩，對于給定的字母馁龟，可以找到多少價值<=50的單詞呢？單詞的價值就是組成一個單詞的所有字母的價值之和漆魔，比如坷檩，單詞ACM的價值是1+3+14=18，單詞HDU的價值是8+4+21=33改抡。(組成的單詞與排列順序無關(guān)矢炼，比如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;
}
