我一开始的思路是最长上升序列......
我真的没见过这种解题的方法......
我以前从没用过pair......
所以我蛮想知道官方题解是啥......
这题按名次DP。
s[pair[l,r]] 表示排名在 [l,r] 内的人数个数。
f[i] 表示排名前 i 的最多的说真话的人数。
对于 f[i] 的状态转移也是比较特别的，对于每一个确定的 r，只考虑从题目给出的数据 (l,r) 的 l 转移。
对应程序是较好理解的，但是我真的不知道这思路咋来......
// q.c
// mark~
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
const int M=1000000+10;
vector<int> q[M];
map<pair<int,int>,int> s;
int f[M];
int main() {
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
int n,l,r;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d%d",&l,&r);
l++,r=n-r;
if(l>r) continue;
s[make_pair(l,r)]++;
if(s[make_pair(l,r)]==1) q[r].push_back(l);
}
for(int i=1;i<=n;i++) {
f[i]=f[i-1];
for(int j=0,k=(int)q[i].size();j<k;j++)
f[i]=max(f[i],f[q[i][j]-1]+min(i-q[i][j]+1,s[make_pair(q[i][j],i)]));
}
printf("%d\n",n-f[n]);
return 0;
}
原文：https://www.cnblogs.com/qjs12/p/8847707.html