题意:
给你一个n行m列的数组,然后里面有0和1,就是从(1,1)走到(n,m),然后其中这些路径走过的0的个数>=a,走过的1的个数>=1,问有多少方案满足条件,对998244353取模。
思考:
第一眼我就感觉是之前noip的方格取数类的题目,然后想设置状态方程,注意到从开始走到结束,一共要走n+m-1个格子,这里完全可以只看路径中经过0的个数,因为总数不变,所以优化掉一维。但是卡到我的是当走到(i,j)这个点的时候这个方案数到底该怎么办。其实可以想到,当不知道咋去转移的时候,可以去闫式dp分析一波,然后可以去枚举当前到了多少个0的时候,再从前面转移即可。因为只能从上面往下走,其实可以再优化掉第一维行,只保留列和0的个数即可。
代码:
int T,n,m;
int ans;
int a,b,l,r;
int va[M][M];
int dp[M][10005];
signed main()
{
IOS;
cin>>n>>m>>a>>b;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cin>>va[i][j];
}
int l = a,r = n+m-1-b;
if(va[1][1]==0) dp[1][1] = 1; //到i列,0的个数为j的方案数
else dp[1][0] = 1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(i==1&&j==1) continue;
int t = (va[i][j]==0);
for(int k=i+j-1;k>=t;k--) //这里要倒着枚举,之前的一题就提及过这个问题。这里我们优化掉了第一维如果k从小到大,当你枚举到大的时候又会从这一层的小的来转移,就相当于用了两次这个t。
dp[j][k] = (dp[j][k-t]+dp[j-1][k-t])%mod;
if(t) dp[j][0] = 0;
}
}
for(int i=l;i<=r;i++) ans = (ans+dp[m][i])%mod;
cout<<ans;
return 0;
}
总结:
多总结总结和推一推方案,当当前的方法走不动的时候,想想之前的做过的类似题目,以及以前的一些套路和操作,总言而止还是多做dp题吧。