CF958C3

首先有 \(\mathcal O(n^2k)\) 的暴力 DP。

设 \(f_{i,j}\) 表示前 \(i\) 个数分成 \(j\) 段的最小和，枚举转移点 \(k\)：\(f_{i,j}=\min\left\{f_{k,j-1}+(s_i-s_k)\bmod p\right\}\)，其中 \(s\) 表示 \(a\) 的前缀和。

这时要注意到关键性质：\(f_{i,j}\equiv s_i\pmod p\)。

证明的话数学归纳一下就好了，大抵就是 \((a+b)\bmod p=((a\bmod p)+(b\bmod p))\bmod p\)。

那么对于 \(f_{i,j}\) 的两个转移点 \(x,y(x\ne y,x,y\lt i)\)，设 \(w_x=(s_i-s_x)\bmod p,w_y=(s_i-s_y)\bmod p\)。

那么就是要在 \(f_{x,j-1}+w_x\) 和 \(f_{y,j-1}+w_y\) 中选最小。

假设 \(f_{x,j-1}\le f_{y,j-1}\)，那么由于 \(f_{x,j-1}+w_x\equiv f_{y,j-1}+w_y\pmod p,w_x,w_y\lt p\)，所以 \(f_{x,j-1}+w_x\) 一定不大于 \(f_{y,j-1}+w_y\)。

所以对于每个 \(j\) 记录一下最小的 \(f_{i,j}\) 的位置 \(i\) 即可，从这个 \(i\) 转移来一定是最优的。

时间复杂度 \(\mathcal O(nk)\)。

Code：

#include <bits/stdc++.h>
using namespace std;
const int N = 500005, M = 105;
int n, k, p;
int a[N];
int f[N][M], g[2][M];

void chkmin(int &a, int b) {
	if (a > b) a = b;
}

int main() {
	scanf("%d%d%d", &n, &k, &p); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), a[i] %= p, a[i] = (a[i] + a[i - 1]) % p;
	memset(f, 0x3f, sizeof f), f[0][0] = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= k; ++j)
			f[i][j] = min(f[i][j], f[g[(i - 1) & 1][j - 1]][j - 1] + (a[i] - a[g[(i - 1) & 1][j - 1]] + p) % p);
		for (int j = 0; j <= k; ++j) {
			g[i & 1][j] = g[(i - 1) & 1][j];
			if (f[i][j] < f[g[i & 1][j]][j]) g[i & 1][j] = i;
		}
	}
	printf("%d", f[n][k]);
	return 0;
}

原文地址：http://www.cnblogs.com/Kobe303/p/16848999.html