首页 > 代码库 > 【noi 2.6_9267】核电站(DP)
【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-m][0]=f[i-m-1][0~m-1]=f[i-m-1][m]连等上来的,便是现在的-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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。