https://codeforces.com/contest/1433/problem/F
思路：感觉这道题锻炼dp挺好的。
定义：dp[i][j][l][r] : 在第i行第j位，选了l个数字，且此时模数为r的最大和
然后一般情况是第j个数字从j-1的对应转移过来，类似背包。但是这题这么做的话对于模数r的转移对应的要求的是(x%k+a[i][j]%k)%k=r的这个x。
方便一点的话转化成顺推。即考虑第j+1个数字选还是不选。
对于第i行，第j + 1个数字 1、选择第j + 1个数字 dp[i][j + 1][l][(r + a[i][j + 1]) % k] = dp[i][j][l - 1][r] + a[i][j+1]; 2、不选择第j + 1个数字 dp[i][j + 1][l][r] = dp[i][j][l][r];
同时这个题注意上下层的关系也要转移过来，因为下一层的状态选择需要上一层的决策。
然后每次更新下一层的第0位，就表示上一层模数为r时的最大值
dp[i + 1][0][0][r] = max(dp[i][j + 1][l][r], dp[i + 1][0][0][r]); 答案就是 dp[n + 1][0][0][0] : 第n+1行，第0位，取0个数字，模数为0的总和
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=80;
typedef int LL;
LL dp[maxn][maxn][maxn][maxn];
LL a[maxn][maxn];
int main(void)
{
cin.tie(0);std::ios::sync_with_stdio(false);
LL n,m,k;cin>>n>>m>>k;
for(LL i=1;i<=n;i++){
for(LL j=1;j<=m;j++) cin>>a[i][j];
}
memset(dp,-1,sizeof(dp));
dp[1][0][0][0]=0;
for(LL i=1;i<=n;i++){
for(LL j=0;j<m;j++)
{
for(LL l=0;l<=min(j+1,m/2);l++)
{
for(LL r=0;r<k;r++)
{
///不取第j+1个数
dp[i][j+1][l][r]=max(dp[i][j+1][l][r],dp[i][j][l][r]);
if(l&&dp[i][j][l-1][r]!=-1){
///取第j+1个数
dp[i][j+1][l][(r+a[i][j+1])%k]=max(dp[i][j+1][l][(r+a[i][j+1])%k],dp[i][j][l-1][r]+a[i][j+1]);
}
}
for(LL r=0;r<k;r++){
dp[i+1][0][0][r]=max(dp[i+1][0][0][r],dp[i][j+1][l][r]);
}
}
}
}
cout<<max((LL)0,dp[n+1][0][0][0])<<endl;
return 0;
}
