100% 的数据满足: 1n100000 0ai,bin
好吧... 其实讲完了我还是不会.
抄的题解 2333...
设 f[i]表示前 i 个人最多有多少个人说的是真话.
然后 f[i] = max(f[j-1] + sum[j, i]),sum 是指排名可能的区间为 [l,r] 的人的个数.
然后这样转移是 O(N^2)的.
但是有不少冗余状态, 也就是说, sum[i, j]=0, 为结局我这种情况我们可以对每一个 r 建立一个 vector 存储对应这个 r 的 l.
然后怎么如果硬开空间的话空间复杂度也是 O(N^2)的承受不了, 所以可以用 map;
- #include <iostream>
- #include <cstdio>
- #include <map>
- #include <vector>
- using namespace std;
- inline int read() {
- int res=0;char c=getchar();bool f=0;
- while(!isdigit(c)) {if(c=='-')f=1;c=getchar();}
- while(isdigit(c))res=(res<<3)+(res<<1)+(c^48),c=getchar();
- return f?-res:res;
- }
- int n;
- int f[100005];
- map <pair <int, int>, int> sum;
- vector <int> p[100005];
- int main()
- {
- n = read();
- for (register int i = 1 ; i <= n ; i ++)
- {
- int l = read() + 1, r = n - read();
- if (l> r) continue;
- sum[make_pair(l, r)]++;
- if (sum[make_pair(l, r)] == 1) p[r].push_back(l);
- }
- for (register int i = 1 ; i <= n ; i ++)
- {
- f[i] = f[i-1];
- for (register int j = 0 ; j < p[i].size() ; j ++)
- f[i] = max(f[i], f[p[i][j]-1] + min(sum[make_pair(p[i][j], i)], i - p[i][j] + 1));
- }
- printf("%d\n", n - f[n]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2727901.html