7
7
2015
0

bzoj 1664: [Usaco2006 Open]County Fair Events 参加节日庆祝

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;
}
Category: 动态规划 | Tags: bzoj 动态规划 | Read Count: 357

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com