[haoi2011]a

阅读原文时间：2023年07月15日阅读：2

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

题解：首先，由每个人说的话的内容，我们可以理解为他处在ai+1,n-bi这个区间（分数段）内，且这个区间每个人的分数相等；

有n个这样的区间，可以看出，交叉的区间不能一起选，完全相同的区间可以一起选；

这样我们把相同的区间数目求出来作为这个区间的权值，这个问题就成了带权的选择权值之和最大的不相交的区间问题；

利用动态规划解决即可；

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define FILE "a"
#define LL long long
#define up(i,j,n) for(int i=j;i<=n;i++) #define pii pair
#define piii pair
template inline bool chkmin(T &a,T b){return a>b?a=b,true:false;}
template inline bool chkmax(T &a,T b){return a''){if(ch=='-')f=;ch=gc();}
while(ch<=''&&ch>=''){x=(x<<)+(x<<)+ch-'';ch=gc();}
return f?-x:x;
}
}using namespace IO;
namespace OI{
const int maxn();
struct node{
int x,y;
bool operator<(const node &b)const{return x<b.x||(x==b.x&&y<b.y);}
bool operator==(const node &b){return x==b.x&&y==b.y;}
}a[maxn];
int n,f[maxn];
struct Node{
int y,v,next;
}e[maxn];
int linkk[maxn],len=;
void insert(int x,int y,int v){
e[++len].y=y;
e[len].next=linkk[x];
linkk[x]=len;
e[len].v=v;
}
void slove(){
n=read();
up(i,,n)a[i].x=read()+,a[i].y=n-read();
sort(a+,a+n+);
up(i,,n){
int j=i,v;
while(a[j+]==a[i])j++;
v=j-i+;
if(a[i].y-a[i].x+<v)v=a[i].y-a[i].x+;
insert(a[i].x,a[i].y,v);
i=j;
}
up(i,,n){
chkmax(f[i],f[i-]);
for(int j=linkk[i];j;j=e[j].next)chkmax(f[e[j].y],f[i-]+e[j].v);
}
printf("%d\n",n-f[n]);
}
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
using namespace OI;
slove();
return ;
}

手机扫一扫

移动阅读更方便

你可能感兴趣的文章