洛谷 P2519 [HAOI2011]problem a

传送门

 

考虑转化为求最多说真话的人数

设$f(i)$表示排名前$i$的人中最多说真话的人的数量，考虑转移，如果由$j$转移而来，可以设$[j,i]$之间的人全都分数相等，那么式子就是$f[i]=f[j-1]+sum([j,i])$，其中$sum([j,i])$表示处在这个区间的人数，全部分数相等，另外如果人数多于区间数，多出来的人都在说谎

//minamoto
#include<bits/stdc++.h>
#define mp(i,j) make_pair(i,j)
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
inline int read(){
    #define num ch-'0'
    char ch;bool flag=0;int res;
    while(!isdigit(ch=getc()))
    (ch=='-')&&(flag=true);
    for(res=num;isdigit(ch=getc());res=res*10+num);
    (flag)&&(res=-res);
    #undef num
    return res;
}
const int N=100005;
vector<int> a[N];int n,f[N];map<pair<int,int>,int> x;
vector<int>::iterator ii;
int main(){
//    freopen("testdata.in","r",stdin);
    n=read();
    for(int i=1;i<=n;++i){
        int l=read(),r=read();
        ++l,r=n-r;
        if(l>r) continue;
        if(++x[mp(l,r)]==1) a[r].push_back(l);
    }
    for(int i=1;i<=n;++i){
        f[i]=f[i-1];
        for(ii=a[i].begin();ii!=a[i].end();++ii)
        cmax(f[i],f[(*ii)-1]+min(i-(*ii)+1,x[mp(*ii,i)]));
    }
    printf("%d\n",n-f[n]);
    return 0;
}