洛谷P2519-区间dp

P2519 [HAOI2011]problem a

题目描述

一次考试共有n个人参加，第i个人说：“有ai个人分数比我高，bi个人分数比我低。”问最少有几个人没有说真话(可能有相同的分数)

输入格式

第一行一个整数n，接下来n行每行两个整数，第i+1行的两个整数分别代表ai、bi

输出格式

一个整数，表示最少有几个人说谎

输入输出样例

输入 #1

输出 #1

说明/提示

100%的数据满足： 1≤n≤100000 0≤ai、bi≤n

题解:

犹豫每个人回答的是有几个人分比我高和有几个人分比我低，且能有多个人的分数一样，所以可以有如下转换：

【有几个人分比我高和有几个人分比我低】-》【我的排名在分比我高的人数+1和总人数减去分比我低的】-》我的排名在【l，r】

转换之后每个人的回答就变成了一个个区间[l,r]，那么问题就变成了求最多有几个区间是不相交的（区间相等不算，即l和r都相等不算相交。若没有此条件即可用贪心来求解区间不相交的问题）。所以我们先把l和r都相等的区间合并在一起，即为每一个区间设个价值val，而这个价值的范围为（1 <= val <= r - l + 1 ），原因即为不可能有大于r - l + 1个人在[l,r]区间内。合并之后我们只需要进行dp就好了。

转移方程为dp[i] = max(dp[i - 1],dp[L - 1] + V[j])
dp[L - 1] + V[j]:L为与当前遍历端点相等区间的左区间的大小,j为在与当前遍历右端点相等的区间编号,v[j]为所遍历到区间的价值大小
转移即为:max(不进行更新,在与当前遍历到的右端点相等的区间中找一个最大的不与区间相交的值+相应区间的值)

代码:
for(int i = 1,j = 1;i <= n;i ++)//遍历所有的右端点,对没一个右端点进行更新
{
    dp[i] = dp[i - 1];//继承上一个更新的最优值
    while(j <= tot && R[j] == i)//tot:区间的总个数
    {
        dp[i] = max(dp[i],dp[L[j] - 1] + V[j]);//更新值
        j++;
    }

}
时间复杂度:O(n + tot)

完整代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n;
int dp[maxn],v[maxn];
struct node{
    int l,r;
    friend bool operator < (node a,node b){
        if(a.r != b.r) return a.r < b.r;
        return a.l < b.l;
    }
}nd[maxn],last_nd[maxn];
int main(){
    std::ios::sync_with_stdio(false);
    int l,r,tol = 0,tot = 0;
    cin>>n;
    for(int i = 1;i <= n;i ++){
        cin>>l>>r;
        if(l + r >= n) continue;
        nd[++tol].l = l + 1;
        nd[tol].r = n - r;
    }
    sort(nd + 1,nd + tol + 1);
    for(int i = 1;i <= tol;i ++){
        if(nd[i].l != nd[i - 1].l || nd[i].r != nd[i - 1].r){
            last_nd[++tot].l = nd[i].l;
            last_nd[tot].r = nd[i].r;    
        }
        v[tot] = min(v[tot] + 1,nd[i].r - nd[i].l + 1);
    }
    for(int i = 1,j = 1;i <= n;i ++){
        dp[i] = dp[i - 1];
        while(j <= tot && last_nd[j].r == i){
            dp[i] = max(dp[i],dp[last_nd[j].l - 1] + v[j]);
            j ++;
        }
    }
    cout<<n - dp[n]<<endl;
    return 0;
}