Ignatius and the Princess III HDU

Ignatius and the Princess III HDU - 1028

整数划分问题

假的dp（复杂度不对）

 1 #include<cstdio>
 2 #include<cstring>
 3 typedef long long LL;
 4 LL ans[122][122];
 5 LL n,anss;
 6 LL get(LL x,LL y)
 7 {
 8     if(ans[x][y]!=-1)    return ans[x][y];
 9     if(y==0)    return ans[x][y]=0;
10     if(x<y)        return ans[x][y]=0;
11     ans[x][y]=0;
12     LL i;
13     for(i=0;i<=y;i++)
14         ans[x][y]+=get(x-y,i);
15     return ans[x][y];
16 }
17 int main()
18 {
19     memset(ans,-1,sizeof(ans));
20     ans[0][0]=1;
21     while(scanf("%lld",&n)==1)
22     {
23         anss=0;
24         for(int i=1;i<=n;i++)    anss+=get(n,i);
25         printf("%lld
",anss);
26     }
27     return 0;
28 }

一般的dp

ans[i][j]表示把i拆成最大j的数的方案数。要么分配一个j（剩下ans[i-j][j]），要么一个也不分配（剩下ans[i][j-1]）。

参考

 1 #include<cstdio>
 2 #include<cstring>
 3 typedef long long LL;
 4 LL ans[122][122];
 5 LL n,anss;
 6 LL get(LL x,LL y)
 7 {
 8     if(ans[x][y]!=0)    return ans[x][y];
 9     if(y==0)    return 0;
10     if(x<y)        return ans[x][y]=get(x,x);
11     return ans[x][y]=get(x-y,y)+get(x,y-1);
12 }
13 int main()
14 {
15     ans[0][0]=1;
16     while(scanf("%lld",&n)==1)
17         printf("%lld
",get(n,n));
18     return 0;
19 }

甚至可以写成这样

 1 #include<cstdio>
 2 #include<cstring>
 3 typedef long long LL;
 4 LL ans[122][122];
 5 LL n,anss;
 6 LL get(LL x,LL y)
 7 {
 8     if(x<0)        return 0;
 9     if(ans[x][y]!=0)    return ans[x][y];
10     if(y==0)    return 0;
11     return ans[x][y]=get(x-y,y)+get(x,y-1);
12 }
13 int main()
14 {
15     ans[0][0]=1;
16     while(scanf("%lld",&n)==1)
17         printf("%lld
",get(n,n));
18     return 0;
19 }

母函数做法

参考

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef long long LL;
 6 LL n;
 7 LL ans[122][122];//ans[i][j]存的是到第i个多项式为止指数为j的项数
 8 int main()
 9 {
10     LL i,j,k;
11     while(scanf("%lld",&n)==1)
12     {
13         memset(ans,0,sizeof(ans));
14         ans[0][0]=1;
15         for(i=1;i<=n;i++)
16             for(j=0;j<=n;j+=i)
17                 for(k=0;k<=n-j;k++)
18                     ans[i][k+j]+=ans[i-1][k];
19         printf("%lld
",ans[n][n]);
20     }
21     return 0;
22 }