[HAOI2011]Problem A

题意

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

.

分析

我们可以求最多有多少人说了真话

题目中的 可以转化为,成绩按降序排序,第 个人处在 的区间,这个区间的人的分数与 都相同。

那么把 处理成区间 后,把相同的区间合并,区间的出现次数为该区间的权值 . 显然有以下条件:

  • .
  • .

不满足第一个条件的就删掉,不满足第二个条件的就把权值赋为 .(最多有 个人说了真话)

那么问题转化为,有 个区间,每个区间有一个权值 ,求不相交区间的最大权值和。

鉴于 ,直接 DP 即可

表示 选取区间的最大权值和

代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+5;
int n,n_,tot;
struct data{int l,r,v;};
data a[N];
bool cmp(data x,data y){return x.r==y.r?x.l<y.l:x.r<y.r;}
int f[N];
int main(){scanf("%d",&n);
    n_=n;
    for(int i=1;i<=n_;i++){scanf("%d%d",&a[i].l,&a[i].r),a[i].l++,a[i].r=n-a[i].r;
        if(a[i].l>a[i].r)--i,--n_,++tot;// 条件 1
    }
    sort(a+1,a+1+n_,cmp);
    int cur=0;
    for(int i=1;i<=n_;i++){if(a[i].l==a[i-1].l&&a[i].r==a[i-1].r)++a[cur].v;
        else {a[cur].v=min(a[cur].v,a[cur].r-a[cur].l+1);// 条件 2
            a[++cur]=a[i],a[cur].v=1;
        }
    }
    a[cur].v=min(a[cur].v,a[cur].r-a[cur].l+1);// 条件 2
    int pos=1;
    for(int i=1;i<=n;i++){f[i]=f[i-1];
        while(a[pos].r<=i&&pos<=cur)f[i]=max(f[i],f[a[pos].l-1]+a[pos].v),++pos;
    }
    printf("%d",n_-f[n]+tot);
    return 0;
}


  转载请注明: Sshwy's Blog [HAOI2011]Problem A

 上一篇
[HAOI2010] 软件安装 [HAOI2010] 软件安装
题意有 个软件和空间为 的硬盘,每个软件有一个占用空间 和价值 和一个依赖软件 表示没有依赖)。一个软件要安装,仅当其依赖软件已安装且硬盘空间足够,求最大价值. $N\le
2019.01.16
下一篇 
斜率优化 DP 入门 斜率优化 DP 入门
前言本蒟蒻的第一道斜率优化 DP 前后卡了 3 小时…… 海星 有时候好不容易推出一个 DP 的式子,结果发现数据范围太大? 单调队列无法优化? 那就考虑斜率优化吧 [APIO2014] 序列分割 你正在玩一个关于长度为 的非负整
2019.01.15
  目录