看成背包写二维就好了
用\(f_{i,j}\)表示把\(1\)到\(j\)的叶子归成\(i\)堆所需要的最小体力,状态转移方程太好想了!
以上,网上题解很少,是不是因为这题太水?
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=1005,MAXK=15,INF=99999999;
int f[MAXN][MAXK];
int g[MAXN][MAXN];
int w[MAXN];
int n,k;
int main()
{
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
f[i][1]=f[i-1][1]+(w[i]*(i-1));
}
for (int i=1;i<=n;i++)
for (int j=i;j<=n;j++)
g[i][j]=g[i][j-1]+w[j]*(j-i);
for (int i=2;i<=k;i++)
{
for (int j=i;j<=n;j++)
{
f[j][i]=INF;
for (int l=i;l<=j;l++)
{
f[j][i]=min(f[j][i],f[l-1][i-1]+g[l][j]);
}
}
}
printf("%d\n",f[n][k]);
return 0;
}