有点迷惑,把我注释的那部分取消注释,就错了。但是感觉思路都一样啊。。。。求助大佬
查看原帖
有点迷惑,把我注释的那部分取消注释,就错了。但是感觉思路都一样啊。。。。求助大佬
675572
syyyyhy楼主2022/3/24 10:33
//饥饿的奶牛动态规划
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

ll n;
struct node 
{
	ll be;
	ll va;
};
ll dp[3000020];
vector<node> g[3000020];


int main()
{
	cin>>n;
	ll maxzhong=0;
	for(ll i=1;i<=n;i++)
	{
		ll begin,end;
		cin>>begin>>end;
		ll val=end-begin+1;
		node a;
		a.be=begin-1;  //它要比较的那个元素
		a.va=val; 
		maxzhong=max(maxzhong,end);
		g[end].push_back(a);
	}

	for(ll i=1;i<=maxzhong;i++)
	{
		//if(g[i].size()==0)   
		dp[i]=dp[i-1];
	//	else
	//	{
			for(ll j=0;j<g[i].size();j++)
			{
				node a=g[i][j];
				dp[i]=max(dp[i],dp[a.be]+a.va);
			}
	//	}
	}
	cout<<dp[maxzhong]<<endl;
 } 
2022/3/24 10:33
加载中...