【noi 2.6_9267】核电站（DP）

题意：n个数中不能同时选连续m个或以上，问方案数。

解法：f[i][j]表示从前i个中选，到第i个已经连续选了j个。
j!=0时, =f[i-1][j-1] ; j=0时, =f[i-1][0~m-1] ;

优化1：f[i][m]存f[i-1][0~m-1]，就不用多for一重。

 1 #include<cstdio>

 2 #include<cstdlib>

 3 #include<cstring>

 4 using namespace std;

 5

 6 long long f[55][10];

 7 int main()

 8 {

 9     int n,m;

10     scanf("%d%d",&n,&m);

11     f[1][0]=f[1][1]=1,f[1][m]=2;

12     for (int j=2;j<m;j++) f[1][j]=0;

13     for (int i=2;i<=n;i++)

14     {

15      long long h=0;

16      f[i][0]=f[i-1][m];

17      f[i][1]=f[i-1][0];

18      h=f[i][0]+f[i][1];

19      for (int j=2;j<m;j++)

20      {

21        f[i][j]=f[i-1][j-1];

22        h+=f[i][j];

23      }

24      f[i][m]=h;

25     }

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

27     return 0;

28 }

优化2：（由上面的方程推出）f[i]表示从前i个数中合法的方案数，即之前的f[i][m]。

i<m时，f[i]=2*f[i-1]；每次对于第i个数可选或不选，方案数都各为f[i-1]。
i>=m时，则再-f[i-m-1]；由于i=m时，i-m-1<0则单独写出了来-1（1~m的数都选的状态）。
可知-f[i-m-1]是因为每次f[i-1][]中不合法的都是f[i-1][m-1]，而它也是从最初的 f[i-1][m-1]=f[i-2][m-2]= ... =f[i-m][0]=f[i-m-1][0~m-1]=f[i-m-1][m]连等上来的，也就是说要减去已经连续选了m-1个的方案数：f[i-m-1]。

 1 #include<cstdio>

 2 #include<cstdlib>

 3 #include<cstring>

 4 using namespace std;

 5

 6 long long f[55];

 7 int main()

 8 {

 9     int n,m;

10     scanf("%d%d",&n,&m);

11     f[0]=1;

12     for (int i=1;i<=m;i++) f[i]=2*f[i-1];

13     f[m]--;

14     for (int i=m+1;i<=n;i++) f[i]=2*f[i-1]-f[i-m-1];

15     printf("%lld\n",f[n]);

16     return 0;

17 }

注意——f[n][m]不是答案最大的状态，而是f[n][1]。因此看是否要用long long得看f[n][1]......

巴特西

【noi 2.6_9267】核电站（DP）

最新文章

热门文章