题目链接：https://www.luogu.com.cn/problem/P1043
这道题与石子合并很类似，都是把一个环强制改成一个链，然后在链上做区间dp
要初始化出1~2n的前缀和，方便在O(1)的时间内查询[l,r]区间的和。
f[l][r][h] ->
第一维：左端点；第二维：右端点；第三维：分成了几段。
动态转移方程：
很显然的一个初始化：f[l][r][1]=del(sum[r]-sum[l-1]);
转移：f[l][r][h]=min/max(f[l][r][h],f[l][k][h-1]*del(sum[r]-sum[k]));
注意k的枚举
注意初始化数的大小，尤其是memset，0x3f，0x7f，0xc0等。
AC代码：
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 5 using namespace std; 6 7 int n,m; 8 int a[105],sum[105]; 9 int f1[105][105][105],f2[105][105][105]; 10 int maxn,minn=0x7f; 11 12 inline int del(int x){ 13 return (x%10+10)%10; 14 } 15 16 int main(){ 17 memset(f1,0x3f,sizeof(f1)); 18 scanf("%d%d",&n,&m); 19 for(int i=1;i<=n;i++){ 20 scanf("%d",&a[i]); 21 a[i+n]=a[i]; 22 sum[i]=sum[i-1]+a[i]; 23 } 24 for(int i=1;i<=n;i++) sum[i+n]=sum[i]+sum[n]; 25 for(int l=1;l<=2*n;l++){ 26 for(int r=l;r<=2*n;r++){ 27 f1[l][r][1]=f2[l][r][1]=del(sum[r]-sum[l-1]); 28 } 29 } 30 for(int i=1;i<=n;i++){ 31 for(int l=1;l+i-1<=2*n;l++){ 32 int r=l+i-1; 33 for(int h=2;h<=m;h++){ 34 for(int k=l+h-1;k<r;k++){ 35 f1[l][r][h]=min(f1[l][r][h],f1[l][k][h-1]*del(sum[r]-sum[k])); 36 f2[l][r][h]=max(f2[l][r][h],f2[l][k][h-1]*del(sum[r]-sum[k])); 37 } 38 } 39 } 40 } 41 for(int i=1;i<=n;i++){ 42 maxn=max(maxn,f2[i][i+n-1][m]); 43 minn=min(minn,f1[i][i+n-1][m]); 44 } 45 printf("%d\n%d",minn,maxn); 46 return 0; 47 }
原文：https://www.cnblogs.com/New-ljx/p/12219295.html
