洛谷1043 数字游戏

原题链接

又是一道挺水的类区间\(DP\)。
因为题目给定的是一个环，所以先断环成链再\(DP\)即可。
设\(f[i][j][l]\)表示\(i \sim j\)之间的数分成\(l\)段的最大值，\(g[i][j][l]\)为最小值，\(mod(x)\)为\((x \mod 10 + 10) \mod 10\)，\(s[]\)为断环后的链上数据的前缀和。
则有状态转移方程：

\[f[i][j][l] = \max \limits _{k = i + l - 2} ^ {j - 1} \{ f[i][k][l - 1] \times mod(s[j] - s[k]) \} \]

\[g[i][j][l] = \min \limits _{k = i + l - 2} ^ {j - 1} \{ f[i][k][l - 1] \times mod(s[j] - s[k]) \} \]

初始化\(f[i][j][1] = g[i][j][1] = mod(s[j] - s[i - 1])\)，其余\(g\)数组为无穷大，\(f\)数组为\(0\)。
最后答案就是\(\max \limits _{i = 1} ^ {n} f[i][i + n - 1][m], \min \limits _{i = 1} ^ {n} g[i][i + n - 1][m]\)。

#include<cstdio> #include<cstring> using namespace std; const int N = 110; const int M = 15; int f[N][N][M], g[N][N][M], a[N]; inline int re() {	int x = 0;	char c = getchar();	bool p = 0;	for (; c < '0' || c > '9'; c = getchar())	p |= c == '-';	for (; c >= '0' && c <= '9'; c = getchar())	x = x * 10 + c - '0';	return p ? -x : x; } inline int maxn(int x, int y) { return x > y ? x : y; } inline int minn(int x, int y) { return x < y ? x : y; } inline int mod(int x) { return (x % 10 + 10) % 10; } int main() {	int i, j, k, l, n, m, o;	n = re(); m = re();	o = n << 1;	for (i = 1; i <= n; i++)	a[i + n] = a[i] = re();	for (i = 1; i <= o; i++)	a[i] += a[i - 1];	memset(g, 60, sizeof(g));	for (i = 1; i <= o; i++)	for (j = i; j <= o; j++)	f[i][j][1] = g[i][j][1] = mod(a[j] - a[i - 1]);	for (l = 2; l <= m; l++)	for (i = 1; i + l - 1 <= o; i++)	for (j = i + l - 1; j <= o; j++)	for (k = i + l - 2; k < j; k++)	{	f[i][j][l] = maxn(f[i][j][l], f[i][k][l - 1] * mod(a[j] - a[k]));	g[i][j][l] = minn(g[i][j][l], g[i][k][l - 1] * mod(a[j] - a[k]));	}	int mi = 1e9, ma = 0;	for (i = 1; i <= n; i++)	{	mi = minn(mi, g[i][i + n - 1][m]);	ma = maxn(ma, f[i][i + n - 1][m]);	}	printf("%d\n%d", mi, ma);	return 0; }