Codeforces Contest 958 C2 Encryption (medium) —— dp求划分k个区间，每个区间和最大

This way

题意：

给你n个数，将其划分为k个区间，每个区间的值是这个区间所有值加起来%mod，问你划分后所有区间值的和最大是多少。

题解：

如果暴力for的话是$n^2$的时间复杂度，但是它的mod最大值是100，那么我们就可以开一个三维数组dp[f][i][j]表示到现在为止已经划分了i个区间，最后一个已划分的区间结尾到现在的值的和为j：

假设对于这个数组我们已经划分了两个区间，一个在1后面一个在2后面，那么如果现在到5了，dp的状态就是dp[2][4]，如果到9 了，就是dp[2][9]，但是我们如果在5后面划了一条线，那么在9这个位置就变成了dp[3][0]。 也就是说状态转移方程为

dp[f^1][j][(k+x)%mod]=max(dp[f^1][j][(k+x)%mod],dp[f][j][k]); dp[f^1][j+1][0]=max(dp[f^1][j+1][0],dp[f][j][k]+(k+x)%mod);

注意要用滚动数组，因为开不下那么大的。

#include<bits/stdc++.h> using namespace std; #define ll long long ll dp[2][55][105]; int main() { ll n,k,mod,x; scanf("%lld%lld%lld",&n,&k,&mod); bool f=0; memset(dp,-1,sizeof(dp)); dp[f][0][0]=0; for(int i=1;i<=n;i++) { scanf("%lld",&x); for(int j=0;j<=50;j++) for(int k=0;k<=100;k++) dp[f^1][j][k]=-1; for(int j=0;j<=55;j++) for(int k=0;k<=100;k++) if(~dp[f][j][k]) { dp[f^1][j][(k+x)%mod]=max(dp[f^1][j][(k+x)%mod],dp[f][j][k]); dp[f^1][j+1][0]=max(dp[f^1][j+1][0],dp[f][j][k]+(k+x)%mod); } f^=1; } printf("%lld\n",dp[f][k][0]); return 0; }