TYOI NOIP2012模拟题[T1] 无聊的数列

有一个不下降序列a1≤a2≤…≤an。bi定义为数列中有多少个数严格小于ai，ci定义为数列中有多少个数严格大于ai。
你的秘书把n个数对{(bi, ci) | 1≤i≤n}打乱顺序抄写在一张纸上。由于她很粗心，致使不少数对被抄错了。
你的任务是：改动最少的数对，使得存在与这些数对对应的原数列{ai | 1≤i≤n}。

输入格式：第一行n(n<=1000),表示n个数对
接下来n行，每行两个数b,c。意思和题目描述一样
输出格式：一行，表示要改动的最少数列

Sample Input

5
0 2
0 3
2 1
1 2
4 0

Sample Output

2




看到这题感觉真没啥思路的，做这题告诉我们遇到完全没思路的题真的只能一步步推结论然后慢慢接近正解，感觉自己废了。。。

观察原题面“bi定义为数列中有多少个数严格小于ai，ci定义为数列中有多少个数严格大于a”，可以得到结论每一对给出的数，假如是未被抄错的的话，都可以转化为表示一个数必定在区间[1+b,n-c]中。注意到本题本没有询问具体而只考虑数量。sum[l][r]表示区间l~r内有多少个数，这样我们就理所当然可以统计出一个确定的区间中有多少数，当然一个区间内数的数量不可能超过本区间的长度。因为并非所有数列都是正确的，当统计的数量超过区间长度时，就把区间数的数量赋值为区间长度。

当我们拥有这些数据后，01背包。用dp[i]表示i内最多可以存在的数的数量，求解n内最多可以存在的数的数量，数的数量又转化为区间数，最后简单容斥。

#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
#include<math.h>
#define maxn 1005
using namespace std;
int n;
int sum[maxn][maxn],dp[maxn];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        sum[l+1][n-r]++;
        if(sum[l+1][n-r]>(n-r)-(l+1)+1) 
        sum[l+1][n-r]=(n-r)-(l+1)+1;
    }
    for(int i=1;i<=n;i++)
    for(int j=0;j<i;j++)
    dp[i]=max(dp[i],dp[j]+sum[j+1][i]);
    
    printf("%d",n-dp[n]);
}

TYOI NOIP2012模拟题[T1] 无聊的数列

原文：https://www.cnblogs.com/cubeconcept/p/11406382.html