解题思路:
构建数组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.11 (C语言代码)浏览:475 |
C语言程序设计教程(第三版)课后习题10.2 (C语言代码)浏览:674 |
妹子杀手的故事 (C语言代码)浏览:691 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:327 |
DNA (C语言代码)浏览:540 |
母牛的故事 (C语言代码)浏览:716 |
A+B for Input-Output Practice (IV) (C语言代码)浏览:493 |
小九九 (C语言描述,不看要求真坑爹)浏览:985 |
简单的a+b (C语言代码)浏览:464 |
数列排序 (C语言代码)浏览:617 |