首页 > 代码库 > 洛谷OJ 1373 小a和uim之大逃离 DP
洛谷OJ 1373 小a和uim之大逃离 DP
https://www.luogu.org/problem/show?pid=1373
题意:n*m地图,n,m<=800,起点,终点任意,两个人每次轮流取出点中的数并膜K,问走奇数次 两人取值相同的方法数?
只关心两人取的值是否相等,则记录差值即可
起点和终点任意 则设状态dp[i][j][k][p] 到达点(i,j)差值为k 并且由p取数的方法数
不用枚举起点,暴力把所有状态的方案都计算出来即可,复杂度为O(n*m*k)
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e9+7; const int N=805; int dp[N][N][16][2],n,m,k,a[N][N]; int main() { while(cin>>n>>m>>k) { ll ans=0; memset(dp,0,sizeof(dp)); 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]][0]=1; k++;// for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { for(int l=0;l<k;l++) { //eg:设a得分为s,b得分为t,a-b的差=l-> s-(t+a[i][j]) =l 上局为s-t=l+a[i][j] dp[i][j][l][1]=(dp[i][j][l][1]+dp[i-1][j][(l+a[i][j])%k][0]+dp[i][j-1][(l+a[i][j])%k][0])%mod; //eg:a-b s+a[i][j]-t=l s-t=l-a[i][j] int pre=(l-a[i][j]+k)%k; dp[i][j][l][0]=(dp[i][j][l][0]+dp[i-1][j][pre][1]+dp[i][j-1][pre][1])%mod; } } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { ans=(ans+dp[i][j][0][1])%mod; } } cout<<ans<<endl; } return 0; }
洛谷OJ 1373 小a和uim之大逃离 DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。