P5851 [USACO19DEC]Greedy Pie Eaters P

设 $ K[x][y][z] $ 表示吃 $ z $ 的奶牛且该奶牛喜欢吃的区间在 $ x $ 至 $ y $ 之间。

容易想到 $ K[x][y][z] $ 的转移方程 $ K[x][y][z] = \max( K[x][y][z] , \max ( K[x+1][y][z] , K[x][y-1][z] ) ) $

因为 奶牛们的区间不会重复，所以初始化为

memset(f,0,sizeof(f));
memset(K,0,sizeof(K));
for(int i=1; i<=m; i++)
{
	int x,y,z;
	cin>>z>>x>>y;
	for(int a=x; a<=y; a++)
	{
		K[x][y][a]=z;
	}
}

进一步的 区间 $ f[l][r] $ 的最大值的转移方程为 $ f[l][r]= \max( f[l][r] , f[l][k-1]+g[l][r][k]+f[k+1][r] ) ( l \le k \le r) $

#include<bits/stdc++.h>
using namespace std;
class solves{
	public:
		int n,m;
		int f[305][305];
		int K[305][305][305];
		void work(){
			cin>>n>>m;
			memset(f,0,sizeof(f));
			memset(K,0,sizeof(K));
			for(int i=1; i<=m; i++)
			{
				int x,y,z;
				cin>>z>>x>>y;
				for(int a=x; a<=y; a++)
				{
					K[x][y][a]=z;
				}
			}
			for(int len=1; len<=n; len++){
				for(int i=1; i+len-1<=n; i++){
					int j=i+len-1;
					for(int k=i; k<=j; k++){
						K[i][j][k]=max(K[i][j][k],max(K[i][j-1][k],K[i+1][j][k]));
					}
				}
			}
			for(int len=1; len<=n; len++)
			{
				for(int i=1; i+len-1<=n; i++)
				{
					int j=i+len-1;
					for(int k=i; k<=j; k++){
						f[i][j]=max(f[i][j],f[i][k-1]+K[i][j][k]+f[k+1][j]);
					}
				}
			}
			cout<<f[1][n]<<endl;
		}
}x;
int main(){
	x.work();
}