mipt 004

很经典的题目了。。
一堆人。。有重量和力量之两个属性。。
要堆个塔,一个人头上的所有人重量之和不大于其力量。。
求塔最多能有几个人。。
很明显将人按重量+力量排序。。就可以满足无后效性。。
那么用树状数组维护一下DP的答案就OK了。。
#include<cstdio>
#include<utility>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cstdlib>
#define low(x) (x&(-x))
using namespace std;
typedef pair<int,int> pi;
const int maxs=2000000,maxn=100000;
int n;
pi C[maxs+100];
pi A[maxn];
inline void Renew(pi&x,pi c)
{
if(x.first>c.first) return;
if(x.first<c.first) {x=c;return;}
if(x.second>c.second) x=c;
}
void change(int l,pi d)
{
for(;l<=maxs;l+=low(l))
Renew(C[l],d);
}
pi Max(int l)
{
pi ans=pi(0,0);
for(;l>0;l-=low(l))
Renew(ans,C[l]);
return ans;
}
inline bool cmp(const pi&x,const pi&y)
{return x.first+x.second<y.first+y.second;}
int main()
{
cin>>n;
for(int i=1;i<=maxs;i++)
C[i].second=i,C[i].first=0;
for(int i=0;i<n;i++)
cin>>A[i].first>>A[i].second;
sort(A,A+n,cmp);pi get;int pos;int ans=0;
for(int i=0;i<n;i++)
{
get=Max(A[i].second);
pos=get.second+A[i].first;ans=max(ans,get.first+1);
change(pos,pi(get.first+1,pos));
}
cout<<ans<<endl;
}

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>