luogu2519 [HAOI2011]problem a

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

3
2 0
0 2
2 2

输出样例#1：

1

说明

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

题解

假如有a个人比他高，b个人比他低，那就有n-a+b个人和他一样的。。

把这段人看成一条线段，如果有t个人说的x，y相同，那么这条线段的权重就为t。

那么问题就变成了：有m条线段，每个线段有一个权，求使每条线段长度互不相交的前提下权值最大。

#include <cstdio>
#include <map>
#include <cstdlib>
#define mk make_pair
#define N 100010
using namespace std;
typedef pair<int,int> Pair;
int to[N],next[N],a,b,n,st[N],f[N],tot;
map<Pair,int> ma;
void add(int x,int y)
{
    to[++tot]=y;
    next[tot]=st[x];
    st[x]=tot;
}
main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d",&a,&b);
        if (a+b>=n) continue;
        int t=n-a-b;
        Pair now=mk(a+1,n-b);
        if (!ma[now])
            add(n-b,a+1);
        ma[now]=min(ma[now]+1,t);
    }
    for (int i=1;i<=n;i++)
    {
        f[i]=f[i-1];
        for (int j=st[i];j;j=next[j])
            f[i]=max(f[i],f[to[j]-1]+ma[mk(to[j],i)]);
    }
    printf("%d",n-f[n]);
}