区间DP。
可以看出每行互不影响，所以每次区间DP求出本行最大值，ans即加上每一行最大值。
转移方程式：f[L][R]=max(num[L]*p[k]+dp(L+1,R),dp(L,R-1)+num[R]*p[k])
#include<bits/stdc++.h> #define For(i,l,r) for(int i=l;i<=r;i++) #define lll __int128 #define ll long long using namespace std; const int M=81; int n,m,num[M]; lll ans,p[M],f[M][M]; inline ll read(){ ll f=1,sum=0; char ch=getchar(); while(!isdigit(ch)){if(ch==‘-‘)f=-1;ch=getchar();} while(isdigit(ch)){sum=(sum<<1)+(sum<<3)+(ch^48);ch=getchar();} return f*sum; } inline void write(lll x){ if(x<0) putchar(‘-‘),x=-x; if(x>9) write(x/10); putchar(x%10+‘0‘); } inline lll dp(int l,int r){ if(f[l][r]!=-1) return f[l][r]; if(r-l>=1) f[l][r]=max(num[l]*p[m-r+l]+dp(l+1,r),dp(l,r-1)+num[r]*p[m-r+l]); else f[l][r]=num[l]*p[m-r+l]; return f[l][r]; } int main(){ n=read(),m=read(); p[0]=1; For(i,1,m) p[i]=p[i-1]*2; For(i,1,n){ For(j,1,m) num[j]=read(); memset(f,-1,sizeof(f)); ans+=dp(1,m); } write(ans); return 0; }
#蒟蒻看再久都不知从何下手，神犇一眼秒说是基础递推#
一个比较有趣的dp方程，f[i][j][p][k]中（i,j）表示所处位置，p代表魔夜差值，k代表最后一步是小a还是小uim走。a[i][j]即所处位置魔液值。ans加上f[i][j][0][1]。
转移方程式很好想（+k是避免减出负数）：
f[i][j][p][0]+=f[i-1][j][(p-a[i][j]+k)%k][1]
f[i][j][p][0]+=f[i][j-1][(p-a[i][j]+k)%k][1]
f[i][j][p][1]+=f[i-1][j][(p+a[i][j])%k][0]
f[i][j][p][1]+=f[i][j-1][(p+a[i][j])%k][0]
四维数组注意算空间内存。两次30分因为写成+=，别缩写啦！！
#include<bits/stdc++.h> #define ll long long #define For(i,l,r) for(int i=l;i<=r;i++) using namespace std; const int p=1e9+7; int dp[805][805][20][2]; inline ll read(){ ll f=1,sum=0; char ch=getchar(); while(!isdigit(ch)){if(ch==‘-‘)f=-1;ch=getchar();} while(isdigit(ch)){sum=(sum<<1)+(sum<<3)+(ch^48);ch=getchar();} return f*sum; } int f[805][805][20][2],n,m,k,a[805][805],ans; int main(){ scanf("%d%d%d",&n,&m,&k);++k; For(i,1,n){ For(j,1,m){ scanf("%d",&a[i][j]); f[i][j][a[i][j]%k][0]=1; } } For(i,1,n){ For(j,1,m){ For(h,0,k){ f[i][j][h][0]=(f[i][j][h][0]+f[i-1][j][(h-a[i][j]+k)%k][1])%p; f[i][j][h][0]=(f[i][j][h][0]+f[i][j-1][(h-a[i][j]+k)%k][1])%p; f[i][j][h][1]=(f[i][j][h][1]+f[i-1][j][(h+a[i][j])%k][0])%p; f[i][j][h][1]=(f[i][j][h][1]+f[i][j-1][(h+a[i][j])%k][0])%p; } } } For(i,1,n){ For(j,1,m){ ans=(ans+f[i][j][0][1])%p; } } printf("%d\n",ans); return 0; }
原文：https://www.cnblogs.com/jian-song/p/11624867.html
