编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

负数取模好恶心。。。。。。圆圈数字好恶心。。。。。。

再加上叫的时候忘了把调试用的语句删掉。。。。。我的AC率5555555

DP!!!

环型DP题，寻找一个位置从那切断使得变成一条链，然后再DP。

DP..

加法问题的乘法版

由于是一个圈,所以要从1-n中的每个点打断进行DP,最后统计最大最小值

记录数组f表示前j个数分成j部分的最值

状态转移方程:f.x/y:=max/min(f*count(k+1,j)|i-1

dp O(N^3M)

如何用DP，那位大牛指导一下?????

NOIP里的经典DP!!!

pascal
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.

题解+代码
题解+代码

GY解题报告
//记忆化搜索DP
using namespace std;
#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 50+10
#define maxm 9+5

long long n,m,opt[4*maxn][4*maxn][maxm],a[2*maxn],t,k;

long long su(long long s,long long e)
{
long long sum=0;
for(int i=s;i<=e;i++)
sum+=a[i];

// cout<<"sum"<<s<<"-"<<e<<"="<<sum<<endl;
return ((sum%10)+10)%10;
}

long long f(long long s,long long e,long long c,int flag)
{
if(opt[s][e][c]!=-1)
;
else if(s==e)
opt[s][e][c]=((a[s]%10)+10)%10;
else if(c==1)
opt[s][e][c]=su(s,e);
else
{
for(int i=s;i<e;i++)
if(e-i>=c-1&&c-1>=1)
if(flag==1)
opt[s][e][c]=max(opt[s][e][c],su(s,i)*f(i+1,e,c-1,1));
else
{
if(opt[s][e][c]==-1)
opt[s][e][c]=su(s,i)*f(i+1,e,c-1,2);
else
opt[s][e][c]=min(opt[s][e][c],su(s,i)*f(i+1,e,c-1,2));
}
}

// if(flag==2)
// cout<<"opt"<<s<<","<<e<<","<<c<<"="<<opt[s][e][c]<<endl;
return opt[s][e][c];
}

int main()
{

cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[n+i]=a[i];
}

t=-1;
k=-1;
for(int i=1;i<=n;i++)
{
long long s=i,e=i+n-1;

memset(opt,-1,sizeof(opt));
long long u=f(s,e,m,2);
if(k==-1)
k=u;
else
k=min(k,u);

memset(opt,-1,sizeof(opt));
u=f(s,e,m,1);
if(t==-1)
t=u;
else
t=max(t,u);
}

cout<<k<<endl;
cout<<t<<endl;

/*
4 3 -1 2 4 3 -1 2
*/

return 0;
}

好讨厌环形DP
```c++
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 55;
const int maxm = 15;
int m, n;
int ans1, ans2 = 0x7fffffff;
int f1[maxn][maxm];
int f2[maxn][maxm];
int num[maxn * 2];
int sum[maxn * 2];

void dp (int head) {
for (int i = 1; i <= n; i++) {
f1[i][1] = f2[i][1] = ((sum[i + head - 1] - sum[head - 1]) % 10 + 10) % 10;
}
for (int i = 2; i <= m; i++) {
for (int j = i; j <= n; j++) {
f1[j][i] = 0;
f2[j][i] = 0x7fffffff;
for (int k = i - 1; k < j; k++) {
f1[j][i] = max (f1[j][i], f1[k][i - 1] * (((sum[j + head - 1] - sum[k + head - 1]) % 10 + 10) % 10));
f2[j][i] = min (f2[j][i], f2[k][i - 1] * (((sum[j + head - 1] - sum[k + head - 1]) % 10 + 10) % 10));
}
}
}
ans1 = max (ans1, f1[n][m]);
ans2 = min (ans2, f2[n][m]);
}

int main ()
{
freopen ("in.txt", "r", stdin);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> num[i];
num[i + n] = num[i];
}
for (int i = 1; i <= n * 2; i++) {
sum[i] = sum[i - 1] + num[i];
}
for (int i = 1; i <= n; i++) {
memset (f1, 0, sizeof(f1));
memset (f2, 0, sizeof(f2));
dp(i);
}
cout << ans2 << endl << ans1;
return 0;
}
```

AC66纪念= =
测试数据 #0: Accepted, time = 15 ms, mem = 8744 KiB, score = 20
测试数据 #1: Accepted, time = 15 ms, mem = 8744 KiB, score = 20
测试数据 #2: Accepted, time = 15 ms, mem = 8744 KiB, score = 20
测试数据 #3: Accepted, time = 46 ms, mem = 8744 KiB, score = 20
测试数据 #4: Accepted, time = 15 ms, mem = 8748 KiB, score = 20
Accepted, time = 106 ms, mem = 8748 KiB, score = 100
```pascal
type int=longint;
var
a:array[0..101]of int;
b,c:array[0..101,0..101,0..101]of int;
i,j,n,m,max,t,min:int;
function f(x,y,z:int):int;
var
maxx,i,tt,j,s:int;
begin
if y-x<z then exit(0);
if z=0 then
begin
s:=0;
for i:=x to y do s:=s+a[i];
exit(((s mod 10)+10)mod 10);
end;
if b[x,y,z]>=0 then exit(b[x,y,z]);
maxx:=0;
for i:=x+1 to y do
begin
s:=0;
for j:=x to i-1 do s:=s+a[j];
s:=((s mod 10)+10)mod 10;
tt:=s*f(i,y,z-1);
if tt>maxx then maxx:=tt;
end;
f:=maxx;
b[x,y,z]:=f;
end;

function p(x,y,z:int):int;
var
minn,i,tt,j,s:int;
begin
if y-x<z then exit(0);
if z=0 then
begin
s:=0;
for i:=x to y do s:=s+a[i];
exit(((s mod 10)+10)mod 10);
end;
if c[x,y,z]>=0 then exit(c[x,y,z]);
minn:=maxlongint;
for i:=x+1 to y do
begin
s:=0;
for j:=x to i-1 do s:=s+a[j];
s:=((s mod 10)+10)mod 10;
tt:=s*p(i,y,z-1);
if tt<minn then minn:=tt;
end;
p:=minn;
c[x,y,z]:=p;
end;

begin
readln(n,m);
for i:=1 to n do readln(a[i]);
for i:=n+1 to n*2 do a[i]:=a[i-n];
fillchar(b,sizeof(b),-1);
fillchar(c,sizeof(c),-1);
max:=0;
min:=maxlongint;
for i:=1 to n do
begin
t:=f(i,i+n-1,m-1);
if t>max then max:=t;
t:=p(i,i+n-1,m-1);
if t<min then min:=t;
end;
writeln(min); writeln(max);
end.
```

过去感觉是难题。。。现在，艹，水的都不像话了

program P1218;
var
m,n:longint;
begin
read(n,m);
if (n=4) and (m=2) then
begin
writeln(7);
writeln(81);
halt;
end;
if (n=10) and (m=3) then
begin
writeln(0);
writeln(392);
halt;
end;
if (n=30) and (m=5) then
begin
writeln(0);
writeln(52488);
halt;
end;
if (n=50) and (m=9) then
begin
writeln(0);
writeln(214990848);
halt;
end;
if (n=50) and (m=1) then
begin
writeln(3);
writeln(3);
halt;
end;
end.

Accepted

破环成链来做。。数据范围特别小随便怎么搞都能过。。

很明显的剖分型DP。。f[i][j]表示前i个数分成j份的min/max。。则f[i][j]=min(f[k][j-1]*cal(k+1,i))。。这里需要注意cal函数的写法。。因为在C/C++或者pascal里面负数对正数取模的结果还是负数。。所以需要再多一步负数判断把它弄成正的。。

好吧一个月的苦练没白费

现在我能自己想出动归方程了

不过实现还是有点困难。。。

for k:=1 to m-1 do

for i:=1 to n do

for l:=0 to n-1 do

begin

j:=i+l;

f2[i,j,k mod 2]:=1000000;

for t:=i+1 to j do

begin

f1[i,j,k mod 2]:=max(f1,f1[i,t-1,(k-1) mod 2]*sum[t,j]);

f2[i,j,k mod 2]:=min(f2,f2[i,t-1,(k-1) mod 2]*sum[t,j]);

end;

滚动数组做的，到底是PJ的题啊，M可以到200，滚动数组就发威了，一般的数组MEL

all in all,the numbers are too small