Zq's Blog DP,算法 [DP]bzoj2298: [HAOI2011]problem a

[DP]bzoj2298: [HAOI2011]problem a

题目描述

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

输入

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

输出

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

样例输入

3
2 0
0 2
2 2

样例输出

1

提示

$100\%$的数据满足:$1\le n\le100000,0\le a_i,b_i\le n$

题解

又见DP(鬼知道这10天我经历了什么);

正着算起来麻烦,反着来算,设$F[i]$表示前$i$句话最多有多少人说真话,最后答案就是$n-F[n]$;

我们发现一句话如果为真话,那么$a,b$即为第$a+1$到第$n-b$个人与他的分数相等,可以用一条线段来表示,求$F[i]$即可转化成求前$i$条线段中最多有多少条不相交的线段使得其长度和最大,这里长度即为人数;注意一点如果有多个人说的话是一样的,他们的人数可能会小于这条线段的长度,两者取个$min$即可;

转移需要注意一下,因为要求不相交,从$n-b$到$a+1$建一条有向边就行了;

#include<map>
#include<cstdio>
#include<algorithm>
using namespace std;
map<pair<int,int>,int>Num;
int N,F[100005];
int tot,lnk[100005],son[100005],nxt[100005];
inline void add(int x,int y){son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;}
inline int read(){
    int Res=0;char ch=getchar();
    while (ch>'9'||ch<'0') ch=getchar();
    while (ch>='0'&&ch<='9') Res=Res*10+ch-'0',ch=getchar();
    return Res;
}
int main()
{
    N=read();
    for (int i=1;i<=N;i++){
        int A=read(),B=read();
        A++;B=N-B;
        if (A>B) continue;
        pair<int,int>S=make_pair(A,B);
        if (!Num[S]) add(B,A);
        Num[S]++;
    }
    for (int i=1;i<=N;i++){
        F[i]=F[i-1];
        for (int j=lnk[i];j;j=nxt[j]){
            F[i]=max(F[i],F[son[j]-1]+min(Num[make_pair(son[j],i)],i-son[j]+1));
        }
    }
    printf("%d\n",N-F[N]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注