【noi 2.6_9285】盒子与小球之三（DP）

题意：有N个相同的球，M个不同的盒子，每个盒子最多放K个球。请计算将这N个球全部放入盒子中的方案数模1000007后的结果。

解法：f[i][j]表示i个盒子里放j个球的方案数。

1.得到3重循环的坐法，枚举第i个盒子里放k个球——f[i][j]=sum( f[i-1][j-k~j] )

 1 #include<cstdio>

 2 #include<cstdlib>

 3 #include<cstring>

 4 #include<iostream>

 5 using namespace std;

 6 #define N 5010

 7 #define Mod 1000007

 8

 9 int f[2][N];

10

11 int mmin(int x,int y) {return x<y?x:y;}

12 int main()

13 {

14     int n,m,kk;

15     scanf("%d%d%d",&n,&m,&kk);

16     f[0][0]=1;

17     int u=1;

18     for (int i=1;i<=m;i++)

19     {

20      for (int j=1;j<=n;j++)

21      {

22       f[u][j]=0;

23       for (int k=1;k<=mmin(j,kk);k++)

24         f[u][j]=(f[u][j]+f[1-u][j-k])%Mod;

25      }

26      u=1-u;

27     }

28     printf("%d\n",f[1-u][n]);

29     return 0;

30 }

1 滚动数组

2.用上面的式子利用前缀和的概念（自己稍微画个条形图就好理解很多了）或 f[i][j]与f[i][j-1]的递推式相减可化成这个式子：f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-k-1];

注意——初始化；式子不要粗心写错，否则调试得都是泪啊~ T_T

 1 #include<cstdio>

 2 #include<cstdlib>

 3 #include<cstring>

 4 #include<iostream>

 5 using namespace std;

 6 #define N 5010

 7 #define mod 1000007

 8

 9 int f[N][N];

10 int mmin(int x,int y) {return x<y?x:y;}

11 int main()

12 {

13     int n,m,kk;

14     scanf("%d%d%d",&n,&m,&kk);

15     for (int j=0;j<=kk&&j<=n;j++)

16       f[1][j]=1;

17     for (int i=2;i<=m;i++)

18     {

19      f[i][0]=1;

20      for (int j=1;j<=n;j++)

21      {

22       f[i][j]=(f[i-1][j]+f[i][j-1])%mod;//f[i-1][j]

23       if (j>kk) f[i][j]=(f[i][j]+mod-f[i-1][j-kk-1])%mod;

24      }

25     }

26     printf("%d\n",f[m][n]);

27     return 0;

28 }

巴特西

【noi 2.6_9285】盒子与小球之三（DP）

最新文章

热门文章