[BZOJ2298] [HAOI2011] problem a (dp)

2024-01-01 23:54:46

Description

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

Input

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

Output

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

Sample Input

3
2 0
0 2
2 2

Sample Output

HINT

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

Source

Solution

　　a个人在他前面，b个人在他后面，相当于名次在$[b+1,n-a]$中的人分数一样（分数按非降序排列）

　　如果这个人说的是真话，其对应的区间不会和其他区间相交。

　　$f[i]$表示名次第1~i的人最多有多少人说真话，转移方程看程序，我相信你能理解_(:3 」∠)_

　　哦，，，选取的线段可以重合。

 #include <bits/stdc++.h>

 using namespace std;

 #define fir first

 #define sec second

 map<int, int> Map[];

 map<int, int>::iterator it;

 int f[];

 int main()

 {

     int n, a, b;

     cin >> n;

     for(int i = ; i <= n; i++)

     {

         cin >> a >> b;

         if(n - a > b) Map[b][n - a]++;

     }

     for(int i = ; i < n; i++)

     {

         for(it = Map[i].begin(); it != Map[i].end(); it++)

             f[it->fir] = max(f[it->fir], f[i] + min(it->sec, it->fir - i));

         f[i + ] = max(f[i + ], f[i]);

     }

     cout << n - f[n] << endl;

     return ;

 }

码农公寓