https://codeforces.com/contest/1433/problem/F
用dp[i][j]表示前i行，sum%kp==j的最大值是多少
然后发现每一层可以说是独立的，所以对于每一行，f[j][l][k]表示前j列已经选了l个sum%kp==k的最大值是多少
每一行跑完以后再选出对于这一行的每个k最大的f[m][l][k](l=0->m/2)是多少，再用这个mx去从上一行dp[i-1][tk]更新这一行dp[i][(tk+k)%kp]
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxl=75; const int inf=1e9+10; int n,m,kp,len,cnt,tot,cas,ans; int a[maxl][maxl]; int dp[maxl][maxl]; int f[maxl][maxl][maxl]; bool vis[maxl]; char s[maxl]; inline void prework() { scanf("%d%d%d",&n,&m,&kp); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); } inline void upd(int &x,int y){x=max(x,y);} inline void solv(int i) { memset(f,-1,sizeof(f)); f[0][0][0]=0; for(int j=0;j<m;j++) for(int l=0;l<=len;l++) for(int k=0;k<kp;k++) if(f[j][l][k]>=0) { upd(f[j+1][l][k],f[j][l][k]); if(l<len) upd(f[j+1][l+1][(k+a[i][j+1])%kp],f[j][l][k]+a[i][j+1]); } } inline void mainwork() { memset(dp,-1,sizeof(dp)); dp[0][0]=0;len=m/2;int mx; for(int i=1;i<=n;i++) { solv(i); for(int k=0;k<kp;k++) { mx=-1; for(int l=0;l<=len;l++) mx=max(mx,f[m][l][k]); if(mx<0) continue; for(int tk=0;tk<kp;tk++) if(dp[i-1][tk]>=0) upd(dp[i][(tk+k)%kp],dp[i-1][tk]+mx); } } } inline void print() { printf("%d",dp[n][0]); } int main() { int t=1; //scanf("%d",&t); for(cas=1;cas<=t;cas++) { prework(); mainwork(); print(); } return 0; }
