【HAOI2011】Problem A

题解

问题A
传送门

下午考试结果讲过的题还是挂掉了QwQ

题目大意就是判断一下几个人说出的排名不合法。
判断不合法，需要进行多次比较，实在是不舒服，我们可以利用emm，补集思想。
什么是补集思想，就是说，我考虑的时候考虑的不是答案，而是不能作为答案的个数。
在这个题上，就表现为，有几个人说的话是真的。

因为每个人发的言表示的其实是一个区间，那么可以将整个排名理解为一个数轴，而每个人发的言相当于把自己放在了一条有端点的线段上;而这条有端点的线段上有几个人说真话就可以视为这条线段的贡献。因为排名线段重叠的话会不合法，所以实际上就是找一定量不相互覆盖的线段覆盖数轴并使他们总贡献最大。

那么使用f[i]代表到达第i位最大总贡献，对于f[i]，有f[i]=f[j]+sum[j,i]其中0<j<i且j为以i结尾的一个线段的左端点，sum[j,i]为这条线段的贡献，值等于min(i-j+1,cnt[j,i]，cnt[j,i]为线段的覆盖次数。(因为最多只能有线段长度的人在这个线段上)。

对于区间的记录，覆盖，找相同等操作，可以适当使用STL。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
using namespace std;
const int maxn=100010;
int f[maxn];
vector <int> ask[maxn];//记录线段，因为我使用的是刷表法，所以记录右端点对应的左端点更为自然
map <pair<int,int>,int> Index;//记录线段的权值
int n,m,k,l,r;
void beg(){
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
}
int main(){
    beg();
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        int less,more;scanf("%d%d",&less,&more);
        int l=less+1,r=n-more;//我们的线段是左右均为闭区间，所以加1
        Index[make_pair(l,r)]++;
        if (Index[make_pair(l,r)]==1) ask[r].push_back(l);
    }
    for (int i=1;i<=n;i++){
        f[i]=f[i-1];//我可以完全不用线段覆盖这个点
        for (int j=0;j<ask[i].size();j++){
            int to=ask[i][j];
            f[i]=max(f[i],f[to-1]+min(i-to+1,Index[make_pair(to,i)]));//上面说过方程了
        }
    }
    printf("%d",n-f[n]);//我们求的是补集，记得补回来
}

所以蒟蒻HAOI签到题还是不会做。