[BZOJ2298] [HAOI2011] problem a (dp)

Description

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

Input

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

Output

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

Sample Input

3
2 0
0 2
2 2

Sample Output

1

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 ;
}
上一篇:oracle数据库锁表


下一篇:Asp.Net MVC学习总结(三)——过滤器你怎么看?