地址：https://vijos.org/p/1218
题意：在你面前有一圈整数（一共n个），你要按顺序将其分为m个部分，各部分内的数字相加，相加所得的m个结果对10取模后再相乘，最终得到一个数k。游戏的要求是使你所得的k最大或者最小。

我的做法：
环形DP。先割环为链，枚举断点。
dp[i][j]:取长度为i割为j段能获得的最小(最大)值。
那么dp[i][j] = max{dp[i - k][j - 1] * chuli(sum[s + i] - sum[s + i - k])}
s是第一断点（断环的第一个，k为新增长度）
坑点就是j = 1的情况..也许是我的算法比较特殊需要特殊处理......还有就是负数mod...
1A，看代码
[code lang="cpp"]
#include<cstdio>
#include<iostream>
using namespace std;
int n, m;
int a[500];
int sum[500];
int dp[500][500];
int dp2[500][500];
int chuli(int a){
a %= 10;
if (a < 0) return (10 + a) % 10;
return a % 10;
}
int main(){
int ans = 0;
int ans2 = 0x3f3f3f3f;
cin >> n >> m;
for (int i = 1; i <= n; i++){
cin >> a[i];
a[i + n] = a[i];
}
sum[0] = 0;
for (int i = 1; i <= 2 * n; i++) sum[i] += sum[i - 1] + a[i];
for (int s = 0; s < n; s++){//第几位开始
for (int i = 0; i < 500; i++)
for (int j = 0; j < 500; j++) {
if (i == 0 || j == 0) dp[i][j] = 1, dp2[i][j] = 1;
else dp[i][j] = -0x3f3f3f3f, dp2[i][j] = 0x3f3f3f3f;
}
for (int i = 1; i <= n; i++)//长度
for (int j = 1; j <= min(i, m); j++)//断开几段
{
if (j == 1)//只有一段就不用枚举了
{
dp[i][j] = dp2[i][j] = chuli(sum[s + i] - sum[s]);
continue;
}
for (int k = 1; k <= i - j + 1; k++){//长度枚举
dp[i][j] = max(dp[i][j], dp[i - k][j - 1] * chuli(sum[s + i] - sum[s + i - k]));
dp2[i][j] = min(dp2[i][j], dp2[i - k][j - 1] * chuli(sum[s + i] - sum[s + i - k]));
}
}
ans = max(ans, dp[n][m]);
ans2 = min(ans2, dp2[n][m]);

}

cout << ans2 << endl << ans << endl;
}
[/code]