正题

题目链接:https://www.luogu.org/problem/P2519

---

题目大意

$n$个人，第$i$个人说$a_i$个人比他高，$b_i$个人比他低，允许有相同分数，求最少多少人在说谎。

---

解题思路

我们改为求最多有多少人在说真话，我们发现模型可以转换为$[a_i+1,n-b_i]$这段区间的人分数都相同且与以外的不同，那么问题就变为了求最多有多少条不相交且不重合的线段，考虑$dp$。

设$f_i$表示第$i$位置最多有多少条线段，我们有
$$f_i=max\{f_{j-1}+min\{v[i,j],i-j+1\}\}$$

然而这个方程是$O(n^2)$的，但是我们发现这里的$j$只有可能是$i$在左端点的线段的右端点或者是$i$，所以我们只枚举这些就好了。

时间复杂度$O(n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<vector> using namespace std; const int N=101000; int n,dp[N]; map<pair<int,int>,int>v; vector<int>a[N]; int main() {scanf("%d",&n);for(int i=1;i<=n;i++){int l,r;scanf("%d%d",&l,&r);l=l+1;r=n-r;v[make_pair(l,r)]++;a[r].push_back(l);}for(int i=1;i<=n;i++){dp[i]=dp[i-1];for(int j=0;j<a[i].size();j++)dp[i]=max(dp[i],dp[a[i][j]-1]+min(v[make_pair(a[i][j],i)],i-a[i][j]+1));}printf("%d",n-dp[n]); }

总结

以上是生活随笔为你收集整理的P2519-[HAOI2011]problem a【dp】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。