首页 > 代码库 > Nescafe27 探险队（dp)
Nescafe27 探险队（dp)
之前在BZOJ群里请教了下各位神牛。。大概都得出了需要按某个端点排序。。
首先把一开始就不合法的人（即a+b>=n的人删除），然后得出每个人的排名范围：(b,n-a]
考虑dp[i]表示前i个人中最多有多少个人没说谎
按n-a从小到大排序，则n-a的顺序满足dp的拓扑序，当i取得n-a的时候，寻找区间相同的数量m，那么dp[i]=max(dp[i-1],dp[j]+min(m,N-Aj-Bj))
dp效率是O(n)
#include<set>#include<map>#include<cmath>#include<queue>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int N = 100100;#define rep(i,n) for(int i=0;i<n;i++)#define Rep(i,n) for(int i=1;i<=n;i++)#define For(i,l,r) for(int i=l;i<=r;i++)int n,x,y,dp[N],cnt;pair<int,int> poi[N];bool equal(pair<int,int> A,pair<int,int> B){return (A.first==B.first&&A.second==B.second);}bool cmp(pair<int,int>A,pair<int,int> B){ if(A.second==B.second) return A.first<B.first; else return A.second<B.second;}int main(){ scanf("%d",&n); Rep(i,n){ scanf("%d%d",&x,&y); if(x+y>=n) continue; poi[++cnt]=make_pair(y,n-x); } sort(poi+1,poi+cnt+1,cmp); dp[0]=0;int j=1; Rep(i,n){ dp[i]=dp[i-1]; if(poi[j].second==i){ while(j<=cnt&&poi[j].second==i){ int k=j; while(equal(poi[j],poi[k])&&k<=cnt) k++; dp[i]=max(dp[i],dp[poi[j].first]+min(k-j,poi[j].second-poi[j].first)); j=k; } } } printf("%d\n",n-dp[n]); return 0;}
Nescafe27 探险队（dp)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。