题解：P1043 [NOIp 2003 普及组] 数字游戏
NewbieZZZ
·
·
题解
你说得对，但是这是 T2。（
解法
区间 DP or 划分 DP。
前置部分
（都是小问题，相信你喵。）
首先，又是一圆圈，怎么办？当然是破环成链，把数组复制……等等，可以用队列模拟一个环！每次需要用到队首的时候，取出 Ta，再放回队尾就可以了。方便又快捷。
维护环的起点，要在每次循环后，将队首弹出再重新加入队列。
本题需要用到区间和进行得分计算，所以自然而然地想到维护前缀和。（由于我用了队列模拟环，所以代码里我直接对原数组进行原地前缀和计算，不额外使用空间。）
注：为了防止出现模运算后得到负数得分，我们可以在前缀和计算时利用模运算的性质，去除负数（显然此推论成立）：
推论 若 a\equiv c\pmod n,b \equiv d\pmod n，则 a+c \equiv b+d\pmod n 。
题中要求将总和模 10，我们可以给原数加上一个模 10 得 0 的较大值，如加上 10^8：a[i] = (a[i]+100000000) % 10，这样不影响任何绝对值小于等于 10^8 的整数的得分计算。
dp 部分
我们可以想到，这道题应该是一个区间 dp。这种 dp 一般是这样解决的：
令状态 f_{i,j} 表示将 [i,j] 的所有元素合并能获得的价值的最值，那么 f_{i,j}=\max / \min\{f_{i,k}+f_{k+1,j}+val\}，其中 val 为将这两组元素合并起来的价值。
但在这题中，这种状态较难设计。我们不妨直接设 dp_{i,j} 表示将前 i 个数分成 j 个部分，所能达到的最大得分。（最小得分为 f_{i,j}，同理。）
这样设计状态，我们要先枚举 j，后枚举 i。这样才能保证无后效性。
（要开始推状态转移方程了哟。）
区间 dp 还有一个思想：枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最值，得到原问题的最值。
在这题中，我们可以将分割点设在第 j-1 个区间与第 j 个区间之间，这样可以方便递推实现。（将前面 j-1 个小区间的得分先计算，再合并到第 j 个区间）
我们可以从小数字中试图寻找普遍规律。（其中 k(1\le k<i) 表示分割点）
dp_{i, 1} = & \max\left\{s_{i} \bmod 10\right\} \\
dp_{i, 2}=&\max\left(dp_{k, 1}\times(s_{i} - s_{k}) \bmod 10 \right)\\
dp_{i, 3}=&\max\left(dp_{k, 2}\times(s_{i} - s_{k}) \bmod 10 \right)\\
\cdots
\end{aligned}
我们发现，分成 j 段的价值等价于分成 j-1 段的价值和分割出的第 j 个区间 [k, i] 的价值之和。
即：
dp_{i, j} = \max \left\{dp_{k, j-1} \times\left(s_{i} - s_{k}\right)\bmod 10 \right\}
其实，上文的状态表示和方程，主要与划分 dp 有关。我们用区间 dp 的思想，一步一步推出了划分 dp 的一般方程（把模数去掉就是了），可以看出很多类型的 dp 之间是有内在关联的。
---
（啊，推出来了，算你厉害。但你一定忘了什么！）
首先，我们要求最大（小）得分，所以我们要把 dp 数组全部初始化为一个极小（大）值。
$1$ 段的情况怎么办？\
只有一段，得分显然是这一段的和模 $10$ 的绝对值。即 $f_{i,1}=dp_{i,1}=|sum_i \bmod 10|$。（代码里我用了上文处理的方法）
最后，别忘了统计每次 $dp_{n, m}$ 和 $f_{n,m}$ 的最值。
### 代码
（考察你码力的时候到了，操起键盘吧。一切伟大的思想，都有一个微不足道的开始。）
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long // 防人之心不可无
int dp[2025][20], a[2025], f[2025][20];
int n, m, ans = -1e9, now = 2e9;
signed main(){
queue<int> q;
cin >> n >> m;
for(int i=1; i<=n; ++i){
cin >> a[i];
q.push(a[i]);
}
for(int _=1; _<=n; ++_){ // 用队列模拟要进行 n 次操作
for(int i=1; i<=n; ++i) {
int x = q.front();
q.pop();
a[i] = x; // 更新数组
q.push(x);
}
for(int i=0; i<=n; ++i) {
for(int j=0; j<=m; ++j){
dp[i][j] = -1e9, f[i][j] = 1e9;
}
}
for(int i=1; i<=n; ++i) {
a[i] += a[i-1]; // 原地前缀和
a[i] = (a[i]+1000000000) % 10;
f[i][1] = dp[i][1] = (a[i]+1000000000) % 10;
}
for(int j=2; j<=m; ++j){
for(int i=j; i<=n; ++i){
for(int k=1; k<i; ++k){
dp[i][j] = max(dp[i][j], dp[k][j-1] * ((a[i] - a[k] + 1000000000) % 10));
f[i][j] = min(f[i][j], f[k][j-1] * ((a[i] - a[k] + 1000000000) % 10));
} // 转移
}
}
ans = max(ans,dp[n][m]);
now = min(now, f[n][m]); // 统计答案
int x = q.front();
q.pop();
q.push(x); // 更新这个环的状态
}
cout << now << '\n' << ans;
return 0;
}
```
时间复杂度约为 $\Theta(n^3 m)$，空间复杂度为 $\Theta(nm)$。
（唔，写完了，懂了。赶紧给作者点个赞吧。）
### 鸣谢
感谢所有管理大大的审核。
管理员 @[Acoipp](https://www.luogu.com.cn/user/674469) 巨佬指出了本文一处概念性错误！
End.