CF#677 (Div. 3) F. Zero Remainder Sum (dp)

原题链接

题意：

给你n*m的矩阵，k。求从每一行取不超过m/2（下取整）个数加起来。最终总和modk为0的最大和

题解：

首先对每一行的列进行dp， 设$f[j][cnt][t]$ 前 j 列，取cnt个数，modk为t的最大和。

再对每一行进行dp，设$dp[i][j]$ 前 i 行，modk为 j 最大和

然后枚举前一行的模k后ja，和当前行的模k后jb。 前i-1行最大和为$dp[i-1][ja]$ 当前行最大和为$f[m][0-m/2][jb]$（枚举一下取的个数） 前i行最大和为$dp[i][(ja+jb)\%k]$

最终答案为$dp[n][0]$

#include<bits/stdc++.h> using namespace std; typedef long long ll; #define inf 0x3f3f3f3f #define fi first #define se second #define pii pair<int,int> const int N=75; int a[N][N]; int n,m,k,f[N][N][N],dp[N][N];//f前j列，取cnt个数，modk为t的最大和。dp：前i行，modk为j最大和 int main() { cin>>n>>m>>k; memset(dp,-1,sizeof dp); dp[0][0]=0; for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++)cin>>a[i][j]; memset(f,-1,sizeof f); //f[0][0][0]=0; for(int j=0;j<=m;j++)f[j][0][0]=0;//前j个数取0个模k必然为0，是合法的 for(int j=1; j<=m; j++) for(int cnt=1; cnt<=m/2; cnt++) for(int t=0; t<k; t++) { if(f[j-1][cnt][t]>=0)f[j][cnt][t]=max(f[j][cnt][t],f[j-1][cnt][t]);//不取第j个数 int x=(a[i][j]+t)%k; if(f[j-1][cnt-1][t]>=0)f[j][cnt][x]=max(f[j-1][cnt-1][t]+a[i][j],f[j][cnt][x]); //若取第j个数，之前的模k为t，则取了以后为(a[i][j]+t)%k } for(int tn=0; tn<k; tn++)//当前行模为tn { int x=-1; for(int cnt=0; cnt<=m/2; cnt++)x=max(x,f[m][cnt][tn]);//当前行模为tn最大和 if(x<0)continue; for(int tb=0;tb<k;tb++)//前一行模为tb if(dp[i-1][tb]>=0)dp[i][(tn+tb)%k]=max(dp[i][(tn+tb)%k],dp[i-1][tb]+x); } } cout<<dp[n][0]; return 0; }