题目链接：https://ac.nowcoder.com/acm/contest/1168/H
注解代码里有，大致思路就是把输入数据转换成线段，有重复的线段可以累加，但是最大不能超过该线段的长度，然后找出最大的不重合区间，其他没计入的都是说谎的人
#include<bits/stdc++.h> #include<vector> #include<map> #include<queue> #define LL long long #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; int dp[100005]; struct node { int l; int r; }a[100005]; bool cmp(node x, node y) { if(x.r == y.r) return x.l < y.l; else return x.r < y.r; } int main() { int n, x, y, pos = 1; scanf("%d", &n); for(int i = 1;i <= n;i++) { scanf("%d%d", &x, &y); if(x+y < n) //防止出现负数 { a[pos].l = x+1; //求出这个人所在区间 a[pos].r = n-y; pos++; } } sort(a+1, a+pos+1, cmp); //排序，以右区间为判断条件，小的在前面，右区间相同的左区间小的在前面 int j = 1, flag = 0; for (int i = 1;i <= n;i++) { dp[i] = dp[i-1]; //dp记录当前说真话的人数 while(a[j].r < i) //右区间比i小的都是说谎的人 { j++; if(j > 100000) //当j大于n时跳出循环，否则会段错误 { flag = 1; break; } } int temp = 0; while(a[j].r == i) //如果在一个说谎的人之后是数个右区间相同的人，这里会直接从最后一个开始遍历 { //因为当a[j].r大于i时整个循环只会进行dp数组的传递和i++ if(a[j].l == a[j-1].l) //左区间也相同时累加 temp++; else temp = 1; dp[i] = max(dp[i], dp[a[j].l-1] + min(temp, i - a[j].l + 1));// j++; //dp[a[j].l-1]是上一段不重合的区间 } if(flag) //前面a[j].r都小于i时j会一直加到100000，此时dp[n]的值是0 { //所以需要从n开始往前回溯到有值的dp[i]再把值赋给dp[n] for(int i = n;i >= 1;i--) { if(dp[i]) { dp[n] = dp[i]; break; } } break; } } printf("%d ", n-dp[n]); return 0; }
这道题洛谷，bzoj上面都有，但是华交好像加了几组数据，卡了我好久………没后台数据就是难找bug，还是codeforces好啊