题目链接Pl868

我觉得我的代码没问题，但是就是有问题，改了好久还是没有找到哪里不对，只能求助大佬了,具体问题是比如第二个点答案1995，我的却是2万多，是什么情况没考虑仔细吗？

思路：

首先对区间按x进行从小到大的排序，开一个数组dp[i]记录前i个排好序的区间可以吃到的最大堆数，在求dp[i]时，如果第i堆与第i-1堆没有交集，则直接dp[i]=dp[i-1]+a[i].z;
还有就是有交集的情况 代码有写

代码如下

#include<algorithm>
using namespace std;
int n;
struct cd
{
	int x;
	int y;
	int z;
}a[150005];
bool flag=false;
int dp[150005];//dp[i]表示前i个排好序的区间最多可以吃到多少堆稻草 
bool cmp(cd a,cd b) 
{
	if(a.x!=b.x)return a.x<b.x;
	 if(a.y!=b.y)return a.y<b.y;
	 return true;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].x>>a[i].y;
		a[i].z=(a[i].y-a[i].x+1);
	 } 
	 sort(a+1,a+n+1,cmp); 
	 for(int i=1;i<=n;i++)
	 cout<<a[i].x<<" "<<a[i].y<<endl; 
	 dp[1]=a[1].z;
	 for(int i=2;i<=n;i++)
	 {
	 	if(a[i].x>a[i-1].y)
	 	{
	 		dp[i]=dp[i-1]+a[i].z;
	 		continue;
		 }
		 int kk=0;
		  flag=false;
		 //如果有重叠就查找到上一个不重叠区间 
		 for(int j=i-1;j>=1;j--)
		 {
		 	if(a[j].y<a[i].x)
			 {
			 kk=dp[j];
			 flag=true;
			 break;
		}
		 }
		 if(flag)dp[i]=max(dp[i-1],kk+a[i].z);//有找到
		 //else dp[i]=max(dp[i-1],a[i].z);//没找到 
	 }
	 cout<<dp[n]<<endl; 
	 return 0;
}