解题思路:
构建数组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++代码)浏览:2783 |
简单的a+b (C语言代码)浏览:530 |
蛇行矩阵 (C语言代码)浏览:753 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:476 |
数字游戏 (C++代码)浏览:1184 |
蚂蚁感冒 (C语言代码)浏览:773 |
筛排处理 (C语言代码)浏览:787 |
C语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:2166 |
C语言程序设计教程(第三版)课后习题6.5 (C语言代码)浏览:496 |
【出圈】 (C++代码)简单循环浏览:640 |