数据比较小 直接爆了 5重
枚举断开的琏 dp[i][j][k] （i-j)区间为第k段 dp[i][j][k] = min(dp[i][j][k],dp[g][i-1][k-1]*s[i][j])(g<=i-1) s[i][j]为i-j的和
最大值类似 不知道为嘛要加50W 很纳闷 加小了就WA
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#define INF 100000
using namespace std;
int a[],dp1[][][],dp2[][][],s[][];
int main()
{
int i,j,k,n,g,o,e,aa,b,c;
while(scanf("%d%d",&n,&k)!=EOF)
{
for(i = ; i <= n ; i++)
scanf("%d",&a[i]);
for(i = ; i <= n ; i++)
a[n+i] = a[i];
for(i = ; i <= *n ; i++)
{
s[i][i] = (a[i]+)%;
for(j = i+ ; j <= *n ; j++)
s[i][j] = (s[i][j-]+a[j]+)%;
}
int minz = INF,maxz=;
for(i = ; i < n ; i++)
{
for(aa = ; aa <= k ; aa++)
for(c = ; c <= *n ; c++)
for(b = ; b <= *n ; b++)
{
dp1[c][b][aa] = INF;
dp2[c][b][aa] = ;
}
for(j = i+ ; j <= i+n-(k-) ; j++)
{
dp1[i+][j][] = s[i+][j];
dp2[i+][j][] = s[i+][j];
}
for(j = ; j <= k ; j++)
{
for(g = i+j ; g <= i+n-(k-j) ; g++)
{
for(e = g ; e <= i+n-(k-j) ; e++)
{
dp1[g][e][j] = INF;
for(o = i+j- ; o < g ; o++)
{
dp1[g][e][j] = min(dp1[g][e][j],dp1[o][g-][j-]*s[g][e]);
dp2[g][e][j] = max(dp2[g][e][j],dp2[o][g-][j-]*s[g][e]);
}
}
}
}
for(j = i+ ; j <= i+n ; j++)
{
maxz = max(maxz,dp2[j][i+n][k]);
minz = min(minz,dp1[j][i+n][k]);
}
}
printf("%d\n%d\n",minz,maxz);
}
return ;
}