本人的代码(有点麻烦,勿喷):
```cpp
#include <bits/stdc++.h>
using namespace std;
int N,K;
int a[210];
long long /*int*/dp[210][10][210];
long long /* int*/imp[210][210];//定义成int类型就错了。。。
int n;
int main()
{
scanf("%d%d",&N,&K);
n=N;
while(n>0)
{
scanf("%d",&a[n]);
n--;
}
for(int i=N+1;i<2*N;i++)
{
a[i]=a[i-N];
}
for(int j=2*N-1;j>=1;j--)
{
for(int i=j;i>=max(j-N,1);i--)
{
if(i==j)
{
imp[i][j]=0;
}
else
{
imp[i][j]=imp[i+1][j]+a[i]*(j-i);
}
}
}
for(int p=1;p<=N;p++)
{
for(int i=1;i<=K;i++)
{
for(int j=p+i-1;j<=p+N-1-K+i;j++)
{
dp[p][i][j]=100000000000;
}
}
}
for(int p=1;p<=N;p++)
{
for(int j=p;j<=p+N-1;j++)
{
dp[p][1][j]=imp[p][j];
}
}
for(int p=1;p<=N;p++)
{
for(int i=2;i<=K;i++)
{
for(int j=p+i-1;j<=p+N-1-K+i;j++)
{
for(int x=j-1;x>p+i-2;x--)
{
dp[p][i][j]=min(dp[p][i-1][x]+imp[x+1][j],dp[p][i][j]);
}
}
}
}
long long ans=dp[1][K][N];
for(int p=2;p<=N;p++)
{
ans=min(ans,dp[p][K][N+p-1]);
}
cout<<ans;
return 0;
}
```
by 喝抹茶的布丁 @ 2017-08-06 16:28:27
![](https://cdn.luogu.com.cn/upload/pic/6775.png)
by 喝抹茶的布丁 @ 2017-08-08 16:21:23
镇楼图。。。
by 喝抹茶的布丁 @ 2017-08-08 16:23:39
哈,1年0回复惨案
fyq啊,老师讲这道题了。。
不过讲了一晚上...................
by 路人丙 @ 2018-10-19 20:50:15