BZOJ1587/叶子合并

Posted on By 二价氢

看成背包写二维就好了

表示把的叶子归成堆所需要的最小体力,状态转移方程太好想了!

以上,网上题解很少,是不是因为这题太水?

#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;
}