• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

「BZOJ2131」免费的馅饼 (DP+树状数组) 总算敲出来了

开发技术 开发技术 5小时前 1次浏览

由于未知不稳定因素,在某些评测机上可能有锅,欢迎指正:

#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
struct data{
	int t,p,v;
	int fir,sec;
	void push(){
		scanf("%d%d%d",&t,&p,&v);
		t<<=1;
	}
	int count(){
		fir=t+p;
		sec=t-p;
	}
}d[maxn];
bool cmp1(data x,data y){return x.fir<y.fir;}
bool cmp2(data x,data y){return x.sec<y.sec;}
int t[maxn];
int f[maxn];
int c[maxn];
int n;
inline int mymax(int x,int y){return x>y?x:y;}
inline int lowbit(int x){return x&(-x);}
inline void add(int x,int num){
	for(int i=x;i<=n;i+=lowbit(i))c[i]=mymax(c[i],num);
}
inline int ask(int x){
	int res=0;
	for(int i=x;i;i-=lowbit(i))res=mymax(c[i],res);
	return res;
}
int main(){
	int w;
	scanf("%d%d",&w,&n);
	for(int i=1;i<=n;i++){
		d[i].push();
		d[i].count();
	}
	sort(d+1,d+1+n,cmp1);
	int tot=0;
	for(int i=1;i<=n;i++)
		if(d[i].fir!=d[i-1].fir)
			d[i].fir=++tot;
	sort(d+1,d+1+n,cmp2);
	int ans=0;
	for(int i=1;i<=n;i++){
		f[i]=ask(d[i].fir)+d[i].v;
		ans=mymax(ans,f[i]);
		add(d[i].fir,f[i]);
	}
	printf("%dn",ans);
	return 0;
} 

数据结构优化的DP太难了(T…T)


程序员灯塔
转载请注明原文链接:「BZOJ2131」免费的馅饼 (DP+树状数组) 总算敲出来了
喜欢 (0)