线性动态规划
处理输入,bag[i]是以i为右界的左界集合
for(int i=0;i<n;i++){
int x,y;
cin>>x>>y;
bag[y].pushback(x);
}
dp[i]是第i个bag的时候不重复的最大草数,为每一个bag[i]的x判断找出最大值
dp[i]=max(dp[i],dp[x-1]+i-x+1);//dp[x-1]是第x-1个bag的时候不重复的最大草,避免了重复
#include <bits/stdc++.h>
using namespace std;
#define N 3000001
vector<int> bag[N];
int n, mx, dp[N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
int x, y;
cin >> x >> y;
bag[y].push_back(x);
mx = max(mx, y);
}
//bag[i]是一系列以i为右界的左界集合
//dp[i]是第i个bag的时候,不重复最大草数
for (int i = 1; i <= mx; i++)
{
dp[i] = dp[i - 1];
for (int j = 0; j < bag[i].size(); j++)
{
int x = bag[i][j];
dp[i] = max(dp[i], dp[x - 1] + i - x + 1);//i-x+1是一个草区间,找出这个草区间+dp[x-1]最大值,dp[x-1]是第x-1个bag的时候不重复的最大草,避免了重复
}
}
cout << dp[mx];
}