(Luogu) P1373 小a和uim之大逃离

本文主要是介绍(Luogu) P1373 小a和uim之大逃离，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

解题思路：这里dp要开4维，dp[i][j][t][p] 代表在 (i,j) 差值为t，p为角色（0为a，1为uim） 选择的方案数 。这样我们只要把dp[i][j][0][1]加起来就是所求的方案数了，其实条件是 dp[i][j][a[i][j]%(k+1)][0]=1; 因为每个点都可以为起点。如何更新状态的，我们这样规定 (A-B+k+1)%(k+1)=t%(k+1)   (A为小a，B为uim )。

如果当前是A选，意义就是 ((A+a[i][j])-B+k+1)%(k+1)=t%(k+1) ------> (A-B+k+1)%(k+1)=(t-a[i][j]+k+1)%(k+1) 即转移过来坐标的差为(t-a[i][j]+k+1)%(k+1),角色为1 即

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

如果当前是B选，意义就是 (A-(B+a[i][j])+k+1)%(k+1)=t %(k+1)------>(A-B+k+1)%(k+1)=(t+a[i][j])%(k+1) 即转移过来坐标的差为(t+a[i][j])%(k+1) ,角色为0 即 (代码写的时候复制粘贴上面的所以就没改)

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

代码如下： 

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<cmath>
#include<sstream>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;
int dp[805][805][20][2];//dp[i][j][t][p] 在(i,j)差值为t，p为角色 0为a，1为uim 的方案数 
int a[805][805];
int n,m,k;
int main(){std::ios::sync_with_stdio(0);cin>>n>>m>>k;for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){cin>>a[i][j];dp[i][j][a[i][j]%(k+1)][0]=1; }}ll ans=0;for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){ for(int t=0;t<=k;++t){dp[i][j][t][0]=( dp[i][j][t][0]+dp[i-1][j][(t-a[i][j]+k+1)%(k+1)][1] )%mod;dp[i][j][t][0]=( dp[i][j][t][0]+dp[i][j-1][(t-a[i][j]+k+1)%(k+1)][1] )%mod;dp[i][j][t][1]=( dp[i][j][t][1]+dp[i-1][j][(t+a[i][j]+k+1)%(k+1)][0] )%mod;dp[i][j][t][1]=( dp[i][j][t][1]+dp[i][j-1][(t+a[i][j]+k+1)%(k+1)][0] )%mod;if(t==0)	ans=(ans+dp[i][j][t][1])%mod;}}}cout<<ans<<endl;return 0;
}

 

这篇关于(Luogu) P1373 小a和uim之大逃离的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---