必会算法好题之滚动数组优化dp
先上个可以提交代码的链接https://ac.nowcoder.com/acm/contest/21592/A
题意：
简单来说就是给你一张二维的图只有0和1，然后你可以向下或者向右移动，要求最后到达(n,m)的方案数
题意还是非常好理解的，而且这个dp也算一个写在脸上了，可问题就是仔细一看数据范围
The first line contains four integers, n, m, p, q(1≤n,m≤500,0≤p,q≤10000).Each of the next n lines contains m space separated integersAi,jA_{i,j}Ai,j(0≤Ai,ji,j≤1), denoting the number in the cell (i,j) of the grid A.
数据范围太大啦！！
思路：
首先通过01可以优化一维，在思考可以发现只需要两维就能进行滚动数组的优化，每次只更新两行，之前由于取mod不清楚一直wa，解决完之后，发现了我在实现滚动数组的时候，如果在当前位置为1时，我的更新是dp[i&1][j][k+1]=dp[(i-1)&1][j][k]+dp[i&1][j-1][k]，但是仔细一想就会发现，如果k=0时，dp[i&1][j][k]是不会更新的，所以还需要这里一点细节
#include<bits/stdc++.h>
using namespace std;
const int maxn=505;
const int mod=998244353;
long long dp[2][maxn][maxn*2];
int a[maxn][maxn];
int main()
{
int i,j,k;
int n,m,p,q;
cin>>n>>m>>p>>q;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
dp[1][1][a[1][1]]=1;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(i==1&&j==1) continue;
for(k=0;k<=1001;k++)
{
if(a[i][j]==1) {
if(k==0) dp[i&1][j][k]=0;
dp[i&1][j][k+1]=dp[(i-1)&1][j][k]%mod+dp[i&1][j-1][k]%mod;
dp[i&1][j][k+1]%=mod;
}
else {
dp[i&1][j][k]=dp[(i-1)&1][j][k]%mod+dp[i&1][j-1][k];
dp[i&1][j][k]%=mod;
}
}
}
}
int cnt1=n+m-1;
long long ans=0;
for(k=q;k<=1000;k++)
{
if(cnt1-k>=p)
{
ans=ans+dp[n&1][m][k]%mod;
ans%=mod;
}
}
cout<<ans<<endl;
return 0;
}
查看28道真题和解析