题解：CF1433F Zero Remainder Sum

· · 题解

前言

这么裸的DP，模拟赛时本蒟蒻竟然没有看出来！！！

正文

题目回忆录

题意

给定一个 n \times m 的矩阵，在每一行中选择最多 \left\lfloor\frac{m}{2}\right\rfloor 的元素，求合法的答案中最大值（合法情况当且仅当这个和为 k 的倍数）。

保证答案合法，且和最大，我们考虑DP，但当前的区间是一个二维矩阵，如果直接设四维状态，感觉又不太好理解，所以我们可以分行处理，设 f_{i,j} 表示当前行选择 i 个数（最多为 \left\lfloor\frac{m}{2}\right\rfloor 个），选择的数的和对 k 取余为 j 的和的最大值是多少，通过我们对于背包的学习，我们易得出DP递推式：

f_{cnt+1,(j+a[i]) \bmod k}=\max(f_{cnt+1,(j+a[i]) \bmod k},f_{cnt,j}+a_i)

同时为了行与行之间的状态好转移，我们用一个一维数组 F_j 表示当前这行选若干个数，和对 k 取余为 j 的和的最大值是多少，此状态显然，对 f 数组去 max 即可得到:

F_j=\max(F_j,f_{cnt,j})

我们考虑对于行与行之间的状态转移，令 g_{i,j} 表示前 i 行余数为 j 的最大贡献，在处理完当前这行的贡献后，我们枚举前 i-1 行的余数 x，和当前这行的余数 y，然后用现在的 F 数组去更新当前这行的 g 数组，处理原理与 F 数组基本相同：

g_{i,(x+y) \bmod k}=\max(g_{i,(x+y) \bmod k},F_y+g_{i-1,x})

这样本题就基本解决了。

#include<bits/stdc++.h>
#define pir pair<int,int>
using namespace std;
typedef long long ll;
const int N=88;
int n,m,k,a[N],f[N][N],g[N][N],F[N];

void work(){
    memset(f,0xef,sizeof(f));
    memset(F,0xef,sizeof(F));
    f[0][0]=0;
    for(int i=1;i<=m;i++){
        scanf("%d",&a[i]);
        for(int cnt=i-1;cnt>=0;cnt--){
            for(int j=0;j<k;j++){
                f[cnt+1][(j+a[i])%k]=max(f[cnt+1][(j+a[i])%k],f[cnt][j]+a[i]);
            }
        }
    }
    for(int cnt=0;cnt<=m/2;cnt++) for(int j=0;j<k;j++) F[j]=max(F[j],f[cnt][j]);
}

int main(){
    scanf("%d%d%d",&n,&m,&k);
    memset(g,0xef,sizeof(g));
    g[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int x=0;x<k;x++) g[i][x]=g[i-1][x];
        work();
        for(int x=0;x<k;x++) 
            for(int y=0;y<k;y++) g[i][(x+y)%k]=max(g[i][(x+y)%k],F[y]+g[i-1][x]);
    }
    printf("%d",g[n][0]);
}
//code subimission time---Zero Remainder Sum---12.10

感谢同机房@chenyuze_2029 大佬的协助。