题目描述
Farmer John has M cows, conveniently labeled 1…M, who enjoy the occasional change of pace from eating grass. As a treat for the cows, Farmer John has baked N pies (1≤N≤300), labeled 1…N. Cow i enjoys pies with labels in the range [li,ri] (from li to ri inclusive), and no two cows enjoy the exact same range of pies. Cow i also has a weight, wi, which is an integer in the range 1…106.
Farmer John may choose a sequence of cows c1,c2,…,cK, after which the selected cows will take turns eating in that order. Unfortunately, the cows don’t know how to share! When it is cow ci’s turn to eat, she will consume all of the pies that she enjoys — that is, all remaining pies in the interval [lci,rci]. Farmer John would like to avoid the awkward situation occurring when it is a cows turn to eat but all of the pies she enjoys have already been consumed. Therefore, he wants you to compute the largest possible total weight (wc1+wc2+…+wcK) of a sequence c1,c2,…,cK for which each cow in the sequence eats at least one pie.
SCORING:
Test cases 2-5 satisfy N≤50 and M≤20.
Test cases 6-9 satisfy N≤50.
输入
The first line contains two integers N and M (1≤M≤N(N+1)/2).
The next M lines each describe a cow in terms of the integers wi,li, and ri.
输出
Print the maximum possible total weight of a valid sequence.
样例输入
2 2
100 1 2
100 1 1
样例输出
200
提示
In this example, if cow 1 eats first, then there will be nothing left for cow 2 to eat. However, if cow 2 eats first, then cow 1 will be satisfied by eating the second pie only.
思路
区间DP找区间的最大值
代码实现
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=305;
const int M=30;
const ll INF=1e18;
const ull sed=31;
const ll mod=1e9+7;
const double eps=1e-12;
typedef pair<int,int>P;
int n,m,dp[N][N],a[N][N],v[N][N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
int w,l,r;
scanf("%d%d%d",&w,&l,&r);
dp[l][r]=a[l][r]=v[l][r]=w;
}
for(int len=2;len<=n;len++)
{
for(int l=1;l+len<=n+1;l++)
{
int r=l+len-1;
for(int k=l;k<=r;k++)
{
a[l][k]=max(max(a[l][k],a[l+1][k]),v[l][r]);
dp[l][r]=max(dp[l][r],dp[l][k-1]+dp[k+1][r]+a[l][k]);
}
}
}
printf("%d\n",dp[1][n]);
return 0;
}