洛谷 1373 小a和uim之大逃离

/* 很容易想到f[i][j][k][l][01] 表示到ij点 两个人得分为kl 01表示这一步谁走的 因为起点不同 路径不同 所以要枚举起点.. 时间复杂度 O(nmk*nmk) 空间复杂度 O(2*nmkk) 超时爆空间..... 40分 */ #include<iostream> #include<cstdio> #include<cstring> #define maxn 810 #define mod 1000000007 using namespace std; int n,m,K,ans,a[maxn][maxn]; int f[210][210][17][17][2]; void Clear(int x,int y) {for(int i=x;i<=n;i++)for(int j=y;j<=m;j++)for(int k=0;k<=K;k++)for(int l=0;l<=K;l++){f[i][j][k][l][0]=0;f[i][j][k][l][1]=0;} } 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]);for(int x=1;x<=n;x++)for(int y=1;y<=m;y++){Clear(x,y);f[x][y][a[x][y]%K][0][0]=1;for(int i=x;i<=n;i++)for(int j=y;j<=m;j++)for(int k=0;k<K;k++)for(int l=0;l<K;l++){if(i+1<=n){f[i+1][j][(k+a[i+1][j])%K][l][0]=(f[i+1][j][(k+a[i+1][j])%K][l][0]+f[i][j][k][l][1])%mod;f[i+1][j][k][(l+a[i+1][j])%K][1]=(f[i+1][j][k][(l+a[i+1][j])%K][1]+f[i][j][k][l][0])%mod;}if(j+1<=m){f[i][j+1][(k+a[i][j+1])%K][l][0]=(f[i][j+1][(k+a[i][j+1])%K][l][0]+f[i][j][k][l][1])%mod;f[i][j+1][k][(l+a[i][j+1])%K][1]=(f[i][j+1][k][(l+a[i][j+1])%K][1]+f[i][j][k][l][0])%mod;}if(k==l)ans=(ans+f[i][j][k][l][1])%mod;}}printf("%d\n",ans);return 0; } /* 其实刚才的状态可以降一维 把kl改为两个人的差值 但是会出现负数 考试的时候想到数组平移 但是答案就不对了.... 然后打了暴力 6层循环 美美的~ 后来终于在眼泪中明白 数组平移个卵... 因为在Mod的意义下 平移之后状态就不对应了 不平移mod完之后在+K不就好了嘛 还有就是傻傻的枚举起点了..赋好初值 从1 1开始就好了吗 反正最后统计方案数 互相之间不影响 */ #include<iostream> #include<cstdio> #include<cstring> #define maxn 810 #define mod 1000000007 using namespace std; int n,m,K,ans,a[maxn][maxn]; int f[maxn][maxn][16][2]; int main() {scanf("%d%d%d",&n,&m,&K);K++;memset(f,0,sizeof(f));for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){scanf("%d",&a[i][j]);f[i][j][a[i][j]%K][0]=1;}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)for(int k=0;k<K;k++){if(i+1<=n){f[i+1][j][(k+a[i+1][j])%K][0]=(f[i+1][j][(k+a[i+1][j])%K][0]+f[i][j][k][1])%mod;f[i+1][j][(k-a[i+1][j]+K)%K][1]=(f[i+1][j][(k-a[i+1][j]+K)%K][1]+f[i][j][k][0])%mod;}if(j+1<=m){f[i][j+1][(k+a[i][j+1])%K][0]=(f[i][j+1][(k+a[i][j+1])%K][0]+f[i][j][k][1])%mod;f[i][j+1][(k-a[i][j+1]+K)%K][1]=(f[i][j+1][(k-a[i][j+1]+K)%K][1]+f[i][j][k][0])%mod;}if(k==0)ans=(ans+f[i][j][k][1])%mod;}printf("%d\n",ans);return 0; }

 

转载于:https://www.cnblogs.com/yanlifneg/p/5813077.html

总结

以上是生活随笔为你收集整理的洛谷 1373 小a和uim之大逃离的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。