luoguP1373 小a和uim之大逃离

时间：2023-12-05 19:11:56

DP专题

题目链接

思路

\(f[i][j][a][b][0/1]\)表示在\((i,j)\)这个格子，小a有a滴魔液，他的伙伴有b滴，上一步是小a（0）或者他的伙伴（1）吸取的魔液。

（显然）数组开不下

#include<iostream>

#include<cstring>

#include<cstdio>

#define LL long long

using namespace std;

const LL mod = 1000000007;

int n,m,k;

int val[805][805],f[105][105][5][5][2];

LL ans;

int main()

{

	scanf("%d%d%d",&n,&m,&k);

	for(int i=1;i<=n;i++)

	 for(int j=1;j<=m;j++)

	  scanf("%d",&val[i][j]);

	for(int i=1;i<=n;i++)

	 for(int j=1;j<=m;j++)

	  f[i][j][val[i][j]][0][0]=1;

	for(int i=1;i<=n;i++)

	 for(int j=1;j<=m;j++)

	 {

	 	for(int a=0;a<=k;a++)

	 	 for(int b=0;b<=k;b++)

	 	 {

	 	 	f[i][j][a][b][0]+=f[i][j-1][a-val[i][j]][b][1];

	 	 	f[i][j][a][b][0]+=f[i-1][j][a-val[i][j]][b][1];

	 	 	f[i][j][a][b][0]%=mod;

	 	 	f[i][j][a][b][1]+=f[i][j-1][a][b-val[i][j]][0];

	 	 	f[i][j][a][b][1]+=f[i-1][j][a][b-val[i][j]][0];

	 	 	f[i][j][a][b][1]%=mod;

	 	// 	cout<<f[i][j][a][b][0]<<"*"<<f[i][j][a][b][1]<<endl;

	 	 }

	 }

	for(int i=1;i<=n;i++)

	 for(int j=1;j<=m;j++)

	  for(int a=0;a<=k;a++)

	   ans=(ans+(LL)f[i][j][k][k][1])%mod;

	printf("%lld\n",ans);

	return 0;

}

窃取题解的思路

\(f[i][j][h][0/1]\) \(h\)表示小a与他的伙伴的魔液的差值。

#include<iostream>

#include<cstdio>

#include<cstring>

#define LL long long

using namespace std;

const int inf=1<<26;

int dp[805][805][20][2];

int n,m,k;

int a[802][805];

const int mod=(int)1e9+7;

int main()

{

	scanf("%d%d%d",&n,&m,&k);++k;

	for(int i=1;i<=n;i++)

	 for(int j=1;j<=m;j++)

	  scanf("%d",&a[i][j]),

	  dp[i][j][a[i][j]%k][0]=1;

	int ans=0;

	for(int i=1;i<=n;i++)

	{

		for(int j=1;j<=m;j++)

		{

			for(int h=0;h<=k;h++)

			{

				dp[i][j][h][0]=(dp[i][j][h][0]+dp[i-1][j][(h-a[i][j]+k)%k][1])%mod;

				dp[i][j][h][0]=(dp[i][j][h][0]+dp[i][j-1][(h-a[i][j]+k)%k][1])%mod;

				dp[i][j][h][1]=(dp[i][j][h][1]+dp[i][j-1][(h+a[i][j])%k][0])%mod;

				dp[i][j][h][1]=(dp[i][j][h][1]+dp[i-1][j][(h+a[i][j])%k][0])%mod;

			}

		}

	}

	for(int i=1;i<=n;i++)

	 for(int j=1;j<=m;j++)

	  ans=(ans+dp[i][j][0][1])%mod;

	printf("%d\n",ans);

	return 0;

}

相关文章