2298: [HAOI2011]problem a
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 1326 Solved: 637Description
一次考试共有n个人参加，第i个人说：“有ai个人分数比我高，bi个人分数比我低。”问最少有几个人没有说真话(可能有相同的分数)Input
第一行一个整数n，接下来n行每行两个整数，第i+1行的两个整数分别代表ai、bi
Output
一个整数，表示最少有几个人说谎
Sample Input
32 0
0 2
2 2
Sample Output
1HINT
100%的数据满足： 1≤n≤100000 0≤ai、bi≤n
Source
【分析】
啊。。主要是这么搞笑的题目我错了2次。。。【还要对拍。。。
题目可以弄成n个区间，意思是这n个区间的分数要一样的。
显然区间不能相交但是可以完全重合。
把完全重合的区间合并起来，就是一个带权的最大不相交区间了。
这个直接DP。。
还有一个我后来错了就是那个区间的权值不能大于那个区间的规模，要取一下min。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 100010 int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;} struct node
{
int x,y,c;
}t[Maxn]; bool cmp(node x,node y) {return x.y==y.y?(x.x>y.x):(x.y<y.y);} int f[Maxn]; int main()
{
int n;
scanf("%d",&n);
int cnt=;
for(int i=;i<=n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(x+y>=n) continue;
t[++cnt].x=x+;t[cnt].y=n-y;t[cnt].c=;
}
sort(t+,t++cnt,cmp);
int p=;
for(int i=;i<=cnt;i++)
{
if(t[i].x==t[p].x&&t[i].y==t[p].y) t[p].c++;
else t[++p]=t[i];
}
for(int i=;i<=p;i++) t[i].c=mymin(t[i].c,t[i].y-t[i].x+);
memset(f,,sizeof(f));
f[]=;t[].y=;
for(int i=;i<=p;i++)
{
if(t[i].y!=t[i-].y||i==)
{
for(int j=t[i-].y+;j<=t[i].y;j++) f[j]=mymax(f[j],f[j-]);
}
f[t[i].y]=mymax(f[t[i].y],f[t[i].x-]+t[i].c);
}
printf("%d\n",n-f[t[p].y]);
return ;
}
2017-04-05 09:55:53