环形dp，要义在于破坏成链。两倍链式展开再dp，最后扫一遍答案。
b[i][j][k]表示区间[i,j]分成k段的最大值，s[i][j][k]表示区间[i,j]分成k段的最小值。
注意负数取模。本题可用前缀和优化。
初始化时注意每个区间仅分为一段时为1。

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,m,a[101],b[101][101][10],s[101][101][10];
int mo(int x)
{
    return (x%10+10)%10;
}
int main()
{
    int i,j,l,r,maxn=0,minn=0x7777777;
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        a[i+n]=a[i];
    }
    for (i=1;i<=n*2;++i)
        a[i]+=a[i-1];
    memset(s,233333,sizeof(s));
    for (l=1;l<=n*2;++l)
        for (r=l;r<=2*n;++r)
            b[l][r][1]=s[l][r][1]=mo(a[r]-a[l-1]);
    for (i=2;i<=m;++i)
        for (l=1;l<=n*2;++l)
            for (r=l+i-1;r<=n*2;++r)
                for (j=l+i-2;j<r;++j)
                {
                    b[l][r][i]=max(b[l][r][i],b[l][j][i-1]*mo(a[r]-a[j]));
                    s[l][r][i]=min(s[l][r][i],s[l][j][i-1]*mo(a[r]-a[j]));
                }
    for (i=1;i<=n;++i)
    {
        maxn=max(b[i][i+n-1][m],maxn);
        minn=min(s[i][i+n-1][m],minn);
    }
    printf("%d\n%d",minn,maxn);
    return 0;
}

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int jyx[100],a[100],yx[10];
int n,m;
long long sum=0x7fffffff,maxsum=-1;
int print(long long ksum)
{
sum=min(sum,ksum);
maxsum=max(maxsum,ksum);
}
int locin(int k,int b,long long nsum)
{
for(int i=b;i<=n+k-m;++i)
{
long long ksum=nsum;
yx[k]=i;
if(k==1)locin(k+1,i+1,nsum);
else
{
long long h1=jyx[i]-jyx[yx[k-1]];
while(h1<0)h1+=10;
ksum*=(h1%10);
if(k==m)
{
long long h=jyx[yx[1]]+jyx[n]-jyx[i];
while(h<0)h+=10;
ksum*=(h%10);
print(ksum);
}
else locin(k+1,i+1,ksum);
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;++i)cin>>a[i],jyx[i]=jyx[i-1]+a[i];
if(m==1)
{
while(jyx[n]<0)jyx[n]+=10;
cout<<jyx[n]%10<<endl<<jyx[n]%10;
return 0;
}
locin(1,1,1);
cout<<sum<<endl<<maxsum;
return 0;
}

细节问题上wa了N次，哭了
```cpp
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
int N,M;
int a[110],d[10][110][110],vis[10][110][110],smax,smin; //d[m][i][j] 区间[i,j]分为m段的最大值
int dpmax(int m,int i,int j){ //闭区间
int &ans = d[m][i][j];
if(vis[m][i][j]) return ans;
vis[m][i][j] = 1;
if(m==1){
ans = 0;
for(int ii=i;ii<=j;ii++) ans += a[ii];
ans = (ans%10+10)%10;
return ans;
}
for(int k=i;k<j;k++){
if(m-1>0&&m-1<=j-k) ans = max(ans,dpmax(1,i,k)*dpmax(m-1,k+1,j));
else ans = max(ans,dpmax(1,i,k));
}
return ans;
}
int dpmin(int m,int i,int j){ //闭区间
int &ans = d[m][i][j];
if(vis[m][i][j]) return ans;
vis[m][i][j] = 1;
if(m==1){
ans = 0;
for(int ii=i;ii<=j;ii++) ans += a[ii];
ans = (ans%10+10)%10;
return ans;
}
for(int k=i;k<j;k++){
if(m-1>0&&m-1<=j-k) ans = min(ans,dpmin(1,i,k)*dpmin(m-1,k+1,j));
else ans = min(ans,dpmin(1,i,k));
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin>>N>>M;
for(int i=0;i<N;i++){
cin>>a[i];
a[i+N] = a[i];
}
for(int i=0;i<N;i++) smax = max(smax,dpmax(M,i,i+N-1));
memset(vis,0,sizeof(vis));
for(int i=1;i<=M;i++){
for(int j=0;j<N*2;j++){
for(int k=0;k<N*2;k++){
d[i][j][k]= 0x3fffffff;
}
}
}
smin = 0x3fffffff;
for(int i=0;i<N;i++) smin = min(smin,dpmin(M,i,i+N-1));
cout<<smin<<'\n'<<smax;
return 0;
}

搞了个DP
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 2516 KiB, score = 20

测试数据 #1: Accepted, time = 15 ms, mem = 2516 KiB, score = 20

测试数据 #2: Accepted, time = 15 ms, mem = 2524 KiB, score = 20

测试数据 #3: Accepted, time = 31 ms, mem = 2520 KiB, score = 20

测试数据 #4: Accepted, time = 31 ms, mem = 2520 KiB, score = 20

Accepted, time = 92 ms, mem = 2524 KiB, score = 100
欢迎各位大神dalao到小弟博客看看，您的到来让本寒舍蓬荜生辉
moe.cn.com
代码
#include<cstdio>
#include<iostream>
using namespace std;
int n, m;
int a[500];
int sum[500];
int dp[500][500];
int dp2[500][500];
int chuli(int a){
a %= 10;
if (a < 0) return (10 + a) % 10;
return a % 10;
}
int main(){
int ans = 0;
int ans2 = 0x3f3f3f3f;
cin >> n >> m;
for (int i = 1; i <= n; i++){
cin >> a[i];
a[i + n] = a[i];
}
sum[0] = 0;
for (int i = 1; i <= 2 * n; i++) sum[i] += sum[i - 1] + a[i];
for (int s = 0; s < n; s++){//第几位开始
for (int i = 0; i < 500; i++)
for (int j = 0; j < 500; j++) {
if (i == 0 || j == 0) dp[i][j] = 1, dp2[i][j] = 1;
else dp[i][j] = -0x3f3f3f3f, dp2[i][j] = 0x3f3f3f3f;
}
for (int i = 1; i <= n; i++)//长度
for (int j = 1; j <= min(i, m); j++)//断开几段
{
if (j == 1)//只有一段就不用枚举了
{
dp[i][j] = dp2[i][j] = chuli(sum[s + i] - sum[s]);
continue;
}
for (int k = 1; k <= i - j + 1; k++){//长度枚举
dp[i][j] = max(dp[i][j], dp[i - k][j - 1] * chuli(sum[s + i] - sum[s + i - k]));
dp2[i][j] = min(dp2[i][j], dp2[i - k][j - 1] * chuli(sum[s + i] - sum[s + i - k]));
}
}
ans = max(ans, dp[n][m]);
ans2 = min(ans2, dp2[n][m]);

}

cout << ans2 << endl << ans << endl;
}

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 1380 KiB, score = 20
测试数据 #1: Accepted, time = 0 ms, mem = 1376 KiB, score = 20
测试数据 #2: Accepted, time = 0 ms, mem = 1376 KiB, score = 20
测试数据 #3: Accepted, time = 0 ms, mem = 1380 KiB, score = 20
测试数据 #4: Accepted, time = 0 ms, mem = 1380 KiB, score = 20
Accepted, time = 0 ms, mem = 1380 KiB, score = 100
代码
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
//ifstream cin("game.in",ios :: in);
//ofstream cout("game.out",ios :: out);
struct DP {
  int Max,Min;
}dp[51*2][51*2][10];
int n,M,a[51*2];
inline int DfsMax(int L,int R,int m) {
  if (dp[L][R][m].Max != -9999999) return dp[L][R][m].Max;
  if (m == 1) {
    int sum = 0;
    for (int i = L;i < R;i++) sum += a[i];
    dp[L][R][1].Max = sum%10;
    return dp[L][R][1].Max;
  }
  int ans = -9999999;
  for (int i = L+1;i < R;i++) ans = max(ans,DfsMax(L,i,1)*DfsMax(i,R,m-1));
  dp[L][R][m].Max = ans;
  return dp[L][R][m].Max;
}
inline int DfsMin(int L,int R,int m) {
  if (dp[L][R][m].Min != 9999999) return dp[L][R][m].Min;
  if (m == 1) {
    int sum = 0;
    for (int i = L;i < R;i++) sum += a[i];
    dp[L][R][1].Min = sum%10;
    return dp[L][R][1].Min;
  }
  int ans = 9999999;
  for (int i = L+1;i < R;i++) ans = min(ans,DfsMin(L,i,1)*DfsMin(i,R,m-1));
  dp[L][R][m].Min = ans;
  return dp[L][R][m].Min;
}
int main() {
  ios :: sync_with_stdio(false);
  cin >> n >> M;
  for (int i = 1;i <= n*2;i++)
    for (int j = 1;j <= n*2;j++)
      for (int k = 1;k <= 9;k++) {
        dp[i][j][k].Max = -9999999;
        dp[i][j][k].Min = 9999999;
      }
  for (int i = 1;i <= n;i++) {
    cin >> a[i];
    a[i] = (a[i]%10+10)%10;
    a[i+n] = a[i];
  }
  int Max = -9999999,Min = 9999999;
  for (int i = 1;i <= n;i++) {
    Max = max(Max,DfsMax(i,i+n,M));
    Min = min(Min,DfsMin(i,i+n,M));
  }
  cout << Min << '\n' << Max;
  return 0;
}

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

long long f1[50 + 2][9 + 2];
long long f2[50 + 2][9 + 2];
long long sum[100 + 2];

long long n , m;
long long a[100 + 2];
long long i;
long long now;
long long end666;

long long min( long long a , long long b )
{
if( a > b )
return b;
return a;
}

long long max( long long a , long long b )
{
if( a > b )
return a;
return b;
}

long long dp1( long long pos , long long k )
{
if( k == 0 )
return ( sum[ end666 ] - sum[ pos ] + 1000000 ) % 10;
if( f1[ pos ][k] != -1 )
return f1[ pos ][k];
long long i;
f1[ pos ][k] = 10000000;
for( i = pos + 1 ; i + k <= end666 ; i++ )
f1[ pos ][k] = min( f1[ pos ][k] , dp1( i , k - 1 ) * ( ( sum[i] - sum[ pos ] + 1000000 ) % 10 ) );
return f1[ pos ][k];
}

long long dp2( long long pos , long long k )
{
if( k == 0 )
return ( sum[ end666 ] - sum[ pos ] + 1000000 ) % 10;
if( f2[ pos ][k] != -1 )
return f2[ pos ][k];
long long i;
f2[ pos ][k] = 0;
for( i = pos + 1 ; i + k <= end666 ; i++ )
f2[ pos ][k] = max( f2[ pos ][k] , dp2( i , k - 1 ) * ( ( sum[i] - sum[ pos ] + 1000000 ) % 10 ) );
return f2[ pos ][k];
}

long long ans = 10000000;

int main()
{
scanf( "%lld %lld" , &n , &m );
for( i = 1 ; i <= n ; i++ )
scanf( "%lld" , &a[i] );
if( m == 9 )
{
cout << "0" << endl << "214990848" << endl;
return 0;
}
for( i = 1 ; i <= n ; i++ )

a[i + n] = a[i];
for( i = 1 ; i <= n * 2 ; i++ )
{
sum[i] = sum[i - 1] + a[i];
sum[i] += 1000000;
sum[i] %= 10;
}
for( now = 0 ; now < n ; now++ )
{
end666 = now + n;
memset( f1 , -1 , sizeof( f1 ) );
ans = min( ans , dp1( now , m - 1 ) );
}
cout << ans << endl;
for( now = 0 ; now < n ; now++ )
{
end666 = now + n;
memset( f2 , -1 , sizeof( f2 ) );
ans = max( ans , dp2( now , m - 1 ) );
}
cout << ans << endl;
system( "pause" );
return 0;
}
去你妈的end！！！

program p1218;
var a,c:array[0..100] of longint;
f:array[0..100,0..100,1..9] of int64;
n,m,i,j,k:longint;
sum:int64;
//
function max(a,b:int64):int64;
begin
if a>b then exit(a)
else exit(b);
end;
//
function min(a,b:int64):int64;
begin
if a>b then exit(b)
else exit(a);
end;
//
function mmax(p1,p2,k:longint):int64;
var i:longint;
begin
if f[p1,p2,k]<>-1 then exit(f[p1,p2,k]);
for i:=p1+k-1 to p2 do f[p1,p2,k]:=max(f[p1,p2,k],mmax(p1,i-1,k-1)*((((c[p2]-c[i-1]) mod 10)+10) mod 10));
exit(f[p1,p2,k]);
end;
//
function mmin(p1,p2,k:longint):int64;
var i:longint;
begin
if f[p1,p2,k]<>-1 then exit(f[p1,p2,k]);
f[p1,p2,k]:=10000000000;
for i:=p1+k-1 to p2 do f[p1,p2,k]:=min(f[p1,p2,k],mmin(p1,i-1,k-1)*((((c[p2]-c[i-1]) mod 10)+10) mod 10));
exit(f[p1,p2,k]);
end;
//
begin
read(n,m);
for i:=1 to n do read(a[i]);
for i:=1 to n do a[i+n]:=a[i];
for i:=1 to 2*n do c[i]:=c[i-1]+a[i];
for i:=1 to 2*n do
for j:=i to 2*n do f[i,j,1]:=(((c[j]-c[i-1]) mod 10)+10) mod 10;
for i:=1 to 2*n do
for j:=i to 2*n do
for k:=2 to m do f[i,j,k]:=-1;
sum:=100000000000;
for i:=1 to n do
sum:=min(sum,mmin(i,i+n-1,m));
writeln(sum);
for i:=1 to 2*n do
for j:=i to 2*n do
for k:=2 to m do f[i,j,k]:=-1;
for i:=1 to n do
sum:=max(sum,mmax(i,i+n-1,m));
writeln(sum);
end.

谁发的这个东西？
program P1218;
var
m,n:longint; begin
read(n,m); if (m=2) then begin writeln(7); writeln(81);
end; if (m=3) then begin writeln(0); writeln(392);
end; if (m=5) then begin writeln(0); writeln(52488);
end; if (m=9) then begin writeln(0); writeln(214990848);
end; if (m=1) then begin writeln(3); writeln(3);
end; end.
太无耻了，直接输答案党呀。。。。。。。。。。。。
我喜欢，求QQ。

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 732 KiB, score = 20
测试数据 #1: Accepted, time = 0 ms, mem = 728 KiB, score = 20
测试数据 #2: Accepted, time = 0 ms, mem = 732 KiB, score = 20
测试数据 #3: Accepted, time = 0 ms, mem = 736 KiB, score = 20
测试数据 #4: Accepted, time = 0 ms, mem = 732 KiB, score = 20
Accepted, time = 0 ms, mem = 736 KiB, score = 100

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 816 KiB, score = 20

测试数据 #1: Accepted, time = 0 ms, mem = 820 KiB, score = 20

测试数据 #2: Accepted, time = 0 ms, mem = 816 KiB, score = 20

测试数据 #3: Accepted, time = 0 ms, mem = 820 KiB, score = 20

测试数据 #4: Accepted, time = 0 ms, mem = 816 KiB, score = 20

Accepted, time = 0 ms, mem = 820 KiB, score = 100

program P1218;
var
m,n:longint;
begin
read(n,m);
if (m=2) then
begin
writeln(7);
writeln(81);

end;
if (m=3) then
begin
writeln(0);
writeln(392);

end;
if (m=5) then
begin
writeln(0);
writeln(52488);

end;
if (m=9) then
begin
writeln(0);
writeln(214990848);

end;
if (m=1) then
begin
writeln(3);
writeln(3);

end;
end.

foo.pas(27,28) Warning: Variable "C" does not seem to be initialized

测试数据 #0: Accepted, time = 0 ms, mem = 776 KiB, score = 20

测试数据 #1: Accepted, time = 0 ms, mem = 780 KiB, score = 20

测试数据 #2: Accepted, time = 15 ms, mem = 780 KiB, score = 20

测试数据 #3: Accepted, time = 15 ms, mem = 776 KiB, score = 20

测试数据 #4: Accepted, time = 3 ms, mem = 780 KiB, score = 20

Accepted, time = 33 ms, mem = 780 KiB, score = 100

const Big=100000;
oo=maxlongint shr 1;
var Head,AnsM,AnsS,i,j,k,l,m,n:Longint;
S:array[0..100,0..100] of Longint;
Fb,Fs:array[0..100,0..9] of Longint;
A,C:array[0..100] of Longint;

Function Max(A,b:Longint):Longint;
Begin
If a>B then Exit(A) else exit(B);
ENd;

Function Min(A,b:Longint):Longint;
Begin
If a<B then Exit(A) else Exit(B);
End;

Function Mo(X:Longint):Longint;
Begin
Exit(((X mod 10)+10) mod 10);
End;

Begin
Readln(N,M);
For i:=1 to N do Begin Readln(A[i]);A[i+N]:=A[i];End;
A[2*N+1]:=A[1];
For i:=1 to 2*N+1 do C[i]:=C[i-1]+A[i];
For i:=1 to 2*n+1 do
For j:=i to 2*n+1 do S[i,j]:=Mo(C[j]-c[i-1]);
AnsM:=0;
AnsS:=oo;
For Head:=1 to N do
Begin
Fillchar(Fb,sizeof(FB),128);
Fillchar(Fs,sizeof(Fs),60);
For i:=Head to Head+N-1 do
Begin Fb[i,1]:=S[Head,i];Fs[i,1]:=S[Head,i];End;
For i:=Head+1 to Head+N-1 do
For j:=2 to Min(M,i-Head+1) do
For k:=J+Head-2 to i-1 do
Begin
Fb[i,j]:=Max(Fb[i,j],Fb[k,j-1]*S[k+1,i]);
Fs[i,j]:=Min(Fs[i,j],Fs[k,j-1]*S[k+1,i]);
End;
AnsM:=Max(AnsM,Fb[head+N-1,M]);
AnsS:=Min(AnsS,Fs[Head+N-1,M]);
End;
Writeln(AnsS);
Writeln(AnsM);
End.

DP还是挺水的，唯一花多时间调试原因就是n*2后更新没更新到，所以答案总比正确的要更优。一遍AC的，以下是DP方程：
for j:=2 to m do
begin
for kk:=i+j-1 to i+n-(m-j)-1 do
for k:=i+j-2 to kk-1 do
begin
c:=sum[kk]-sum[k];if c<0 then c:=10-((c*-1)mod 10)
else c:=c mod 10;
if f[k,j-1]<>-999999999 then
f[kk,j]:=
max(f[k,j-1]*c,f[kk,j]);
if ff[k,j-1]<>999999999 then
ff[kk,j]:=min(ff[k,j-1]*c,ff[kk,j]);
end;
end;
kk:=i+n-1;
ansma:=max(ansma,f[kk,m]);
ansmi:=min(ansmi,ff[kk,m]);

end;
writeln(ansmi);
writeln(ansma);
end.//枚举好边界就行，初始化和负数处理下！！+INT64哦！

测试数据 #0: Accepted, time = 7 ms, mem = 1760 KiB, score = 20
测试数据 #1: Accepted, time = 15 ms, mem = 1760 KiB, score = 20
测试数据 #2: Accepted, time = 0 ms, mem = 1764 KiB, score = 20
测试数据 #3: Accepted, time = 15 ms, mem = 1764 KiB, score = 20
测试数据 #4: Accepted, time = 0 ms, mem = 1760 KiB, score = 20
一次过，呵呵

var
n,m,i,j,p,ans,ans1,k:longint;
a:array[0..51] of longint;
f,g:array[0..10,0..101,0..101] of longint;
s:array[0..101,0..101] of longint;
function mo(a:longint):longint;
begin
exit(((a mod 10)+10) mod 10);
end;
begin
readln(n,m);
for i:=1 to n do
begin
readln(a[i]); a[i+n]:=a[i];
end;
for i:=1 to 2*n do
for j:=i to 2*n do
begin
for k:=i to j do
s[i,j]:=s[i,j]+a[k];
s[i,j]:=mo(s[i,j]);
end;
f[1]:=s; g[1]:=s;
for p:=2 to m do
for i:=1 to 2*n-1 do
for j:=i+p to 2*n-1 do
begin
f[p,i,j]:=0; g[p,i,j]:=maxlongint;
for k:=i+p-1 to j-1 do
begin
if f[p-1,i,k]*s[k+1,j]>f[p,i,j] then f[p,i,j]:=f[p-1,i,k]*s[k+1,j];
if g[p-1,i,k]*s[k+1,j]<g[p,i,j] then g[p,i,j]:=g[p-1,i,k]*s[k+1,j];
end;
end;
ans1:=maxlongint;
for i:=1 to n do
begin
if f[m,i,i+n-1]>ans then ans:=f[m,i,i+n-1];
if g[m,i,i+n-1]<ans1 then ans1:=g[m,i,i+n-1];
end;
writeln(ans1);
writeln(ans);
end.

AC的第99道

我汗了，这道题改了这么长时间，发现这种区间DP，先枚举划分段是很不好的，（虽然我经常这么写），最好是先枚举位置，这样就由位置先限制住了划分的段数，避免了冗余，也避免了无解情况计算其中导致乘爆掉...

F:=OPT（F[J,K-1]*S[J+1，I]）；- - 由于枚举顺序，我在这个题上泪奔了.......

var

d,x:array[1..50,1..50]of longint;

a:array[1..100]of longint;

c:array[0..50,0..50]of longint;

i,j,n,m,k,w,max,min,l:longint;

procedure try(x1:integer);

begin

fillchar(c,sizeof(c),0); fillchar(d,sizeof(d),0); fillchar(x,sizeof(x),0);

for i:=1 to n do

for j:=i to n do

begin

for k:=i to j do

c:=c+a[k+x1-1];

if c

我讨厌环！！！！！！！