我的想法是,如果碰到开始时间相同的就找出这相同开始时间最短的那个一个时间,如果没有就找离它结束时间最近的开始时间,可是这样除了第一个点,剩余的点是全错的,请问,大佬们,可以给我一个反例吗?
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+100;
struct node{
int a,b;
}w[N];
int dp[N],f[N];
inline int cmp(node s1,node s2)
{
return s1.a<s2.a;
}
inline int lower(int L,int R,int x)
{
while(L<R)
{
int mid=(L+R+1)>>1;
if(x>=w[mid].a)
L=mid;
else
R=mid-1;
}
while(w[L].a==x&&L>0)
L--;
return L;
}
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=k;i++)
{
int t;
scanf("%d%d",&w[i].a,&t);
w[i].b=w[i].a+t-1;
}
sort(w+1,w+k+1,cmp);
for(int i=1;i<=k;i++)
f[i]=w[i].a;
memset(dp,0x3f,sizeof(dp));
dp[k+1]=0;
for(int i=k;i>=1;i--)
{
int j=lower_bound(f+i+1,f+1+k,w[i].b)-f;
if(w[i].a==w[i+1].a)
dp[i]=min(dp[i+1],dp[j]+(w[i].b-w[i].a+1));
else
dp[i]=min(dp[i],dp[j]+(w[i].b-w[i].a+1));
/*printf("%d %d \n",w[i].a,j);
for(int j=1;j<=k;j++)
printf("%d ",dp[j]);printf("\n");*/
}
//printf("%d \n",dp[1]);
printf("%d\n",n-dp[1]);
return 0;
}