2013-01-24 18:36:29Morris
[ZJ][環狀DP] d836. NOIP2003 2.数字游戏
內容 ：
丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的，在你面前有一圈整数（一共n个），你要按顺序将其分为m个部分，各部分内的数字相加，相加所得的m个结果对10取模后再相乘，最终得到一个数k。游戏的要求是使你所得的k最大或者最小。
例如，对于下面这圈数字（n=4，m=2）：
2
4 -1
3
当要求最小值时，((2-1) mod 10)×((4+3) mod 10)=1×7=7，要求最大值时，为((2+4+3) mod 10)×(-1 mod 10)=9×9=81。特别值得注意的是，无论是负数还是正数，对10取模的结果均为非负值。
丁丁请你编写程序帮他赢得这个游戏。
輸入說明 ：
输入文件第一行有两个整数，n（1≤n≤50）和m（1≤m≤9）。以下n行每行有个整数，其绝对值不大于104，按顺序给出圈中的数字，首尾相接。
輸出說明 ：
输出文件有两行，各包含一个非负整数。第一行是你程序得到的最小值，第二行是最大值。
範例輸入 ：
4 243-12
範例輸出 ：
781
提示 ：
出處 ：
/**********************************************************************************/
/* Problem: d836 "NOIP2003 2.数字游戏" from NOIP2003普及组第二题 */
/* Language: CPP (1495 Bytes) */
/* Result: AC(4ms, 372KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2013-01-24 15:54:48 */
/**********************************************************************************/
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
int n, m, A[105];
int i, j, k, l;
scanf("%d %d", &n, &m);
for(i = 0; i < n; i++)
scanf("%d", &A[i]), A[n+i] = A[i];
long long sum[105][105] = {};
for(i = 0; i < 2*n; i++) {
long long tmp = 0;
for(j = i; j < 2*n; j++) {
tmp += A[j];
tmp %= 10;
sum[i][j] = (tmp%10+10)%10;
}
}
long long rmx = 0, rmn = 0xfffffff;
for(i = 0; i < n; i++) {
long long dp1[105][15];
long long dp2[105][15];
memset(dp1, 0, sizeof(dp1));//mx
for(k = 0; k < i+n; k++)
for(j = 0; j <= m; j++)
dp2[k][j] = 1000000;
for(k = i; k < i+n; k++) {
for(j = k != i; j < m; j++) {
for(l = k; l < i+n; l++) {
if(k != i)
dp1[l][j+1] = max(dp1[l][j+1], dp1[k-1][j]*sum[k][l]);
else
dp1[l][j+1] = max(dp1[l][j+1], sum[k][l]);
if(k != i)
dp2[l][j+1] = min(dp2[l][j+1], dp2[k-1][j]*sum[k][l]);
else
dp2[l][j+1] = min(dp2[l][j+1], sum[k][l]);
}
}
}
rmx = max(dp1[i+n-1][m], rmx);
rmn = min(dp2[i+n-1][m], rmn);
}
printf("%lld\n%lld\n", rmn, rmx);
return 0;
}