st_nec's Blog

dp水题，方程秒出了= =

方程：

f[i]=max{f[j]} (1<=j<i&&r[j]<l[i])

不过是\(O(n^2)\)的，好虚啊，但它应该满足决策单调性。

直接贴代码：

#include<cstdio>
#include<algorithm>
using namespace std;

struct item{
	int l,r;
}a[10010];

int n,f[10010];

bool cmp(item a,item b){
	return a.l==b.l?a.r<b.r:a.l<b.l;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int l;
		scanf("%d%d",&a[i].l,&l);
		a[i].r=a[i].l+l-1;
	}
	sort(a+1,a+1+n,cmp);
	f[1]=1;
	for(int i=2;i<=n;i++){
		int mx=0;
		for(int j=i-1;j>=1;j--){
			if(a[j].r<a[i].l){
				mx=max(mx,f[j]);
			}
		}
		f[i]=mx+1;
	}
	int mx=0;
	for(int i=1;i<=n;i++){
		mx=max(mx,f[i]);
	}
	printf("%d",mx);
	return 0;
}