考察:区间dp
这题就是一维的棋盘分割.
思路:
f[i][j][k]表示将[i,j]区间分为k份得到的最大值.与棋盘分割不同的是,这道题是一维的,所以我们可以只枚举选上半边就可以枚举到所有方案.也可以枚举选下半边,但是注意这道题要预留足够的空间给进一步选择的上半边和下半边,因为memset初始化后,违法情况会爆数据类型.
那么棋盘切割为什么不能只枚举上半边呢?因为这里枚举只枚举到r-1处,在第r行仍能纵向切割.所以需要从下往上枚举.
此外还需要断环成链,枚举每一个长度为n的区间.
1 #include <iostream>
2 #include <cstring>
3 using namespace std;
4 typedef long long LL;
5 const int N = 110,INF = 0x3f3f3f3f;
6 int m,n,s[N],sum[N],maxn = -INF,minv = INF;
7 int f[N][N][10],g[N][N][10];
8 int get(int x)//memset对给定空间填充给定值.
9 {
10 return (x%10+10)%10;
11 }
12 void solve()
13 {
14 for(int len=1;len<=n;len++)
15 for(int l=1;l+len-1<=2*n;l++)
16 {
17 int r = l+len-1;
18 for(int k=2;k<=m;k++)
19 for(int t=l;t<r;t++)
20 {
21 if(l+k-2<t)
22 {
23 int p1 = get(sum[r]-sum[t]);
24 f[l][r][k] = max(f[l][t][k-1]*p1,f[l][r][k]);
25 g[l][r][k] = min(g[l][t][k-1]*p1,g[l][r][k]);
26 }
27 if(t+1+k-2<r)
28 {
29 int p2 = get(sum[t]-sum[l-1]);
30 f[l][r][k] = max(f[t+1][r][k-1]*p2,f[l][r][k]);
31 g[l][r][k] = min(g[t+1][r][k-1]*p2,g[t+1][r][k]);
32 }
33 }//如果g[l][r][k] 不够取k份,相乘可能会爆long long(int)
34 }
35 }
36 void init()
37 {
38 memset(f,-1,sizeof f);
39 memset(g,0x3f,sizeof g);
40 for(int len=1;len<=n;len++)
41 for(int l=1;l+len-1<=2*n;l++)
42 {
43 int r = l+len-1;
44 f[l][r][1] = g[l][r][1] = get(sum[r]-sum[l-1]);
45 }
46 }
47 int main()
48 {
49 scanf("%d%d",&n,&m);
50 for(int i=1;i<=n;i++) scanf("%d",&s[i]),s[i+n] = s[i];
51 for(int i=1;i<=2*n;i++) sum[i] = sum[i-1]+s[i];
52 init();
53 solve();
54 for(int i=1;i<=n;i++)
55 {
56 maxn = max(maxn,f[i][i+n-1][m]);
57 minv = min(minv,g[i][i+n-1][m]);
58 }
59 printf("%d\n%d\n",minv,maxn);
60 return 0;
61 }