解题思路:
构建数组dp[i][j][k]代表第i层,积木从i到k时可能的情况种类。转移方程为dp[i][j][k]=∑dp[i-1][x][y](x<=j且y>=k),如果依照此方式转移,复杂度为O(n^5),如果我们依照前缀和的思路,即sum[i][j][k],代表第i层,积木从j开始,结尾大于等于k的所有情况和,计算此前缀和的转移方程为sum[i][j][k]=sum[i][j][k+1]+dp[i][j][k],依照这个改进,dp[i][j][k]=∑dp[i-1][x][k] (x<=j),复杂度变为O(n^4)。
注意事项:
因为可能积木在未搭建到顶层停止和一个都不放的情况,故把dp的所有数字加起来,另外还要注意不可能的情况,即有X的位置,还要注意取模。
参考代码:
#include<bits/stdc++.h> using namespace std; #define maxx 110 int n,m; string s; int dp[maxx][maxx][maxx]; int all[maxx][maxx]; //不允许为1 int sum[maxx][maxx][maxx]; int main() { cin>>n>>m; for(int i=n;i>=1;--i) { cin>>s; for(int j=1;j<=m;++j) if(s[j-1]=='X') all[i][j]=1; } for(int j=1;j<=m;++j) for(int k=j;k<=m;++k) {if(all[1][k]==1) break; for(int w=1;w<=j;++w) dp[1][j][k]=1; } for(int j=1;j<=m;++j) for(int k=m;k>=j;--k) sum[1][j][k]=(sum[1][j][k+1]+dp[1][j][k])%mod; for(int i=2;i<=n;++i) { for(int j=1;j<=m;++j) for(int k=j;k<=m;++k) {if(all[i][k]==1) break; for(int w=1;w<=j;++w) dp[i][j][k]=(dp[i][j][k]+sum[i-1][w][k])%mod; } for(int j=1;j<=m;++j) for(int k=m;k>=j;--k) sum[i][j][k]=(sum[i][j][k+1]+dp[i][j][k])%mod; } for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) for(int k=j;k<=m;++k) ans=(ans+dp[i][j][k])%mod; cout<<(ans+1)%mod; }
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题6.1 (C语言代码)浏览:664 |
淘淘的名单 (C语言代码)浏览:1090 |
WU-输入输出格式练习 (C++代码)浏览:1076 |
C语言程序设计教程(第三版)课后习题8.5 (C语言代码)浏览:567 |
简单的a+b (C语言代码)浏览:478 |
C语言程序设计教程(第三版)课后习题9.8 (C语言代码)浏览:608 |
字符串比较 (C语言代码)浏览:680 |
排序算法(选择,插入,冒泡)浏览:774 |
上车人数 (C语言代码)浏览:710 |
C语言程序设计教程(第三版)课后习题8.6 (C语言代码)浏览:585 |