BZOJ 2298: [HAOI2011]problem a【动态规划】

Description

一次考试共有n个人参加,第i个人说:“有ai个人分数比我高,bi个人分数比我低。”问最少有几个人没有说真话(可能有相同的分数)

Input

第一行一个整数n,接下来n行每行两个整数,第i+1行的两个整数分别代表ai、bi

Output

一个整数,表示最少有几个人说谎

Sample Input

3
2 0
0 2
2 2
Sample Output
1
HINT

100%的数据满足: 1≤n≤100000   0≤ai、bi≤n

思路:很明显,有x人比他成绩好,y个人比他成绩差,那剩下的n-x-y个人就是成绩和他相同的了,把这段人看成一条线段,如果有t个人说的x,y相同,那么这条线段的权重就为t,那么问题就变成了:有m条线段,每个线段有一个权,求使每条线段长度互不相交的前提下权值最大。然后就是经典问题了

#include<cstdio>

#include<iostream>

#include<map>

#include<algorithm>

#define maxn 100009

using namespace std;

int head[maxn],next[maxn],point[maxn],n,a,b,now,dp[maxn],n;

map <pair<int,int > ,int>s;

void add(int x,int y){next[++now]=head[x];head[x]=now;point[now]=y;}

int main(){

scanf("%d",&n);

for(int i=1;i<=n;i++){

scanf("%d%d",&a,&b);if(a+b>=n)continue;b=n-b;a++;

if(!s[make_pair(a,b)])add(b,a);s[make_pair(a,b)]=min(s[make_pair(a,b)]+1,b-a+1);

}

for(int i=1;i<=n;i++){

dp[i]=dp[i-1];

for(int j=head[i];j;j=next[j]){

int u=point[j]-1;dp[i]=max(dp[i],dp[u]+s[make_pair(u+1,i)]);

}

}printf("%d\n",n-dp[n]);

return 0;

}

上一篇:NOSQL概念入门


下一篇:JS之for...in和for...of