江西的省赛

A

题意:
给你一个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题吧。

上一篇:c语言,宏相关


下一篇:01背包问题