題目網(wǎng)上都可以找到。
注意初始化s[i][j]的時(shí)候要加上100000而不是10！！！我傻叉子了= =
1: #include <stdio.h>
2: #define MAXINT 10000000
3: #define maxn 200
4:
5: int f[maxn][maxn][maxn][2];//0 max|||| 1 min
6: int s[maxn][maxn];
7: int a[maxn];
8: int n,m;
9: int maxans,minans=MAXINT;
10:
11: void find(int x,int y,int t)
12: {
13: if (f[x][y][t][0]) return;
14: if (t==1)
15: {
16: f[x][y][1][0]=f[x][y][1][1]=s[x][y];
17: return;
18: }
19: for (int k=x+t-1-1;k<y;++k)
20: {
21: find(x,k,t-1);
22: if (f[x][k][t-1][1]*s[k+1][y]<f[x][y][t][1]) f[x][y][t][1]=f[x][k][t-1][1]*s[k+1][y];
23: if (f[x][k][t-1][0]*s[k+1][y]>f[x][y][t][0]) f[x][y][t][0]=f[x][k][t-1][0]*s[k+1][y];
24: }
25: }
26:
27: int main()
28: {
29: freopen("game.in","r",stdin);
30: freopen("game.out","w",stdout);
31:
32: scanf("%d%d",&n,&m);
33: for (int i=1;i<=n;++i)
34: {
35: scanf("%d",&a[i]);
36: a[i+n]=a[i];
37: }
38: for (int i=1;i<=2*n;++i)
39: for (int j=i;j<=2*n;++j)
40: for (int k=1;k<=m;++k)
41: f[i][j][k][1]=MAXINT;
42: for (int i=1;i<=2*n;++i)
43: for (int j=i;j<=2*n;++j)
44: s[i][j]=(s[i][j-1]+a[j]+100000)%10;
45: for (int i=1;i<=n;++i) find(i,i+n-1,m);
46: for (int i=1;i<=n;++i)
47: {
48: if (f[i][i+n-1][m][0]>maxans) maxans=f[i][i+n-1][m][0];
49: if (f[i][i+n-1][m][1]<minans) minans=f[i][i+n-1][m][1];
50: }
51: printf("%d\n%d\n",minans,maxans);
52: return 0;
53: }
54: