Codeforces 1433F. Zero Remainder Sum (线性DP)

Description Examples

input 3 4 3 1 2 3 4 5 2 2 2 7 1 1 4 output 24

input 5 5 4 1 2 4 2 1 3 5 1 2 4 1 5 7 1 2 3 8 7 1 2 8 4 7 1 6 output 56

Solution dp[i][d][k] : 在第 $i$行选择$d$个数($d+d<=m$)的和 $\%mod==k$ 的最大值 dp2[i][k]: 在第 $i$行选择若干数(不大于$m/2$)的和 $\%mod==k$ 的最大值 res[i][k]: 前 $i$行选择若干数(不大于$m/2$)的和 $\%mod==k$ 的最大值

故res[n][0]的值即为所求

Code

const int maxn = 70 + 7; const int inf = 1e9 + 7; int mp[maxn][maxn]; int dp[maxn][maxn][maxn], dp2[maxn][maxn]; int res[maxn][maxn]; int main(){ int n,m,mod;scanf("%d%d%d",&n,&m,&mod); memset(dp,-1,sizeof(dp)); memset(dp2,-1,sizeof(dp2)); for(int i = 1;i <= n;++i) for(int j = 1;j <= m;++j) scanf("%d",&mp[i][j]); for(int i = 1;i <= n;++i) { dp[i][0][0] = 0; for(int j = 1;j <= m;++j) { for(int d = min(j,m/2);d >= 1;--d) { for(int k = 0;k < mod;++k) { if(dp[i][d-1][k] != -1) dp[i][d][(k+mp[i][j])%mod] = max(dp[i][d][(k+mp[i][j])%mod], dp[i][d-1][k] + mp[i][j]); } } } for(int k = 0;k < mod;++k) { for(int d = 0;d + d <= m;++d) { if(dp[i][d][k] != -1) dp2[i][k] = max(dp2[i][k], dp[i][d][k]); } } } memset(res,-1,sizeof(res)); res[0][0] = 0; for(int i = 1;i <= n;++i) { res[i][0] = max(res[i][0],0); for(int k1 = 0;k1 < mod;++k1) { for(int k2 = 0;k2 < mod;++k2) { if(res[i-1][k1] != -1 && dp2[i][k2] != -1) res[i][(k1+k2)%mod] = max(res[i][(k1+k2)%mod], res[i-1][k1] + dp2[i][k2]); } } } printf("%d\n", max(0,res[n][0])); return 0; }