1.Subset Sums 集合 这一道题目，我们可以用到背包问题的方案计数，那么用f[i]表示和为i的方案数，可以推出状态转移方程:f[i]=f[j-i]（j=m/2,i），m为所有数的和。 具体看代码：
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<iostream> using namespace std; int n,ans,a[41],mu; long long f[10001]; int main() { freopen("sub.in","r",stdin); freopen("sub.out","w",stdout); int i,j,k,m; scanf("%d",&n); for(i=1; i<=n; i++) { a[i]=i; mu+=i; } if(mu%2) { cout<<0<<endl; return 0; } m=mu; f[0]=1; for(i=1; i<=n; i++) for(j=m/2; j>=i; j--) f[j]+=f[j-i]; printf("%lld",f[m/2]/2); return 0; }2.Longest Prefix 最长前缀 这一题有许多坑，注意标注了**的地方。 思想如下： 我们可以把每一个元素看成背包中的代价（就是重量），那么他的长度就是他的价值，又因为每一个物件可以取无数个，所以就成了一个完全背包。
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<iostream> using namespace std; char s[251][11],kkk[200001]; char c[500001],d[11]; int n,ans,a[251],f[500001]; int pipei(int j,int i){ for(int k=0;k<a[j];k++) if(s[j][k]!=c[i+k])return 0; return 1; } int maxn(int a,int b){ return a>b?a:b; } void dfs(int i){ for(int j=1;j<=n;j++){ if(pipei(j,i)==1 && strlen(s[j])+i<strlen(c)){ ans=maxn(ans,i+strlen(s[j])); dfs(i+strlen(s[j])); } } } void inser(int j,int k){ for(int i=j;i<k;i++) d[i-j]=c[i]; } int pd(int j){ for(int i=0;i<a[j];i++) if(d[i]!=s[j][i])return 0; return 1; } int main(){ freopen("prefix.in","r",stdin); freopen("prefix.out","w",stdout); int i,j,k,m; while(!feof(stdin)){ scanf("%s",s[++n]); if(s[n][0]=='.'){ n--;break; } a[n]=strlen(s[n]); // puts(s[n]); } scanf("\n"); while(cin>>kkk){ strcat(c,kkk); } m=strlen(c); // dfs(0); f[0]=1; for(i=1;i<=m;i++) for(j=1;j<=n;j++) if(i>=a[j]) if(f[i-a[j]]){ int ll=0; memset(d,0,sizeof(d)); for(k=i-a[j];k<i;k++) d[ll++]=c[k]; // puts(d); if(!strcmp(d,s[j]))f[i]=1; } for(i=strlen(c);i>=0;i--) if(f[i]){ cout<<i<<endl; return 0; } return 0; }3.Zero Sum 和为零 这一题我本以为要什么高深的算法，竟然搜索+栈处理（中缀求和）就AC了。
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> #include<iostream> using namespace std; int a[11],n,d[11],sum,ans,p[11]; void out(){ for(int i=1;i<=n;i++){ if(d[i]){ printf("%d",d[i]); if(i==n)break; if(p[i]==1)printf("+"); else if(p[i]==2)printf("-"); else if(p[i]==3)printf(" "); } } puts(""); } int calc(){ int kkk=n,rj=0,i; for(i=1;i<=n;i++){ int x=0,k=i; while(p[i]==3){ x=x*10+d[i++]; } if(i<=n)x=x*10+d[i]; a[++rj]=x; } // out(); int come=2; for(i=1;i<=n;i++) if(p[i]!=3){ if(p[i]==1) a[1]=a[1]+a[come++]; else a[1]=a[1]-a[come++]; } return a[1]; } void dfs(int i){ for(int j=1;j<=3;j++){ if(j==1)p[i]=3; else if(j==2)p[i]=1; else p[i]=2; if(i<n-1)dfs(i+1); else if(calc()==0){ ans++;out(); } } } int main(){ freopen("sum.in","r",stdin); freopen("sum.out","w",stdout); int i,j,k,m; scanf("%d",&n); for(i=1;i<=n;i++){ d[i]=i; } p[n]=3; dfs(1); // printf("%d\n",ans); return 0; }4.Money Systems 货币系统 这如同第一题，也是背包问题的方案计数，重点记住要开long long，而且循环的顺序也有坑，不信你可以试试
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> #include<iostream> using namespace std; long long ans=0; int n,v; long long f[10001],a[26]; int main(){ freopen("money.in","r",stdin); freopen("money.out","w",stdout); int i,j,k; scanf("%d%d",&v,&n); for(i=1;i<=n;i++){ scanf("%lld",&a[i]); } f[0]=1; for(i=1;i<=v;i++) for(j=1;j<=n;j++) if(j>=a[i])f[j]=f[j]+f[j-a[i]]; printf("%lld\n",f[n]); return 0; }