[USACO19DEC]Greedy Pie Eaters

题目

区间dp啊，设(dp_{l,r})表示只考虑(lleq l_ileq r_ileq r)的牛(i)能取到的最大收益

每次新加入一头牛就必然会在([l,r])中新选择至少一个位置，我们枚举这个位置(k)，那么就有(dp_{l,r}=max_{k=l}^r{dp_{l,k-1}+dp_{k+1,r}+g_{l,k,r}})，(g_{l,k,r})表示最大满足(lleq l_ileq kleq r_ileq r)的牛的(w_i)

于是我们就可以跑这个区间dp了，(g)可以滚动一维

代码

#include<bits/stdc++.h>
#define re register
#define max(a,b) ((a)>(b)?(a):(b))
const int maxn=305;
int w[maxn][maxn],dp[maxn][maxn],f[maxn][maxn],n,m;
int main() {
	scanf("%d%d",&n,&m);
	for(re int k,l,r,i=1;i<=m;i++)scanf("%d%d%d",&k,&l,&r),f[l][r]=dp[l][r]=w[l][r]=k;
	for(re int len=2;len<=n;++len)
		for(re int l=1,r=len;r<=n;++l,++r) {
			for(re int k=l;k<=r;++k) {
				f[l][k]=max(max(f[l][k],f[l+1][k]),w[l][r]);
				dp[l][r]=max(dp[l][r],dp[l][k-1]+dp[k+1][r]+f[l][k]);
			}
		}
	printf("%d
",dp[1][n]);return 0;
}