【洛谷2519】[HAOI2011] problem a（动态规划）

点此看题面

大致题意： 一次考试共有\(n\)个人参加，第\(i\)个人说有\(a_i\)个人分数比他高，\(b_i\)个人分数比他低。求最少有几个人说谎。

动态规划

刚看完题目可以说是一头雾水。

仔细想想，可以把每个人的状态转化为一个区间（\([a_i+1,n-b_i]\)），表示这个区间内所有元素都相等。

那么我们要求的就是求出最大的区间数\(Max\)，使这些区间两两之间要么重合，要么不相交，然后用\(n\)减去\(Max\)即为答案。

考虑将区间左边界排个序，就变成了一个类似于求最长上升子序列的过程，这可以做到\(O(NlogN)\)。

呃，好像成了一道普及组难度的水题......

代码

#include<bits/stdc++.h>

#define max(x,y) ((x)>(y)?(x):(y))

#define min(x,y) ((x)<(y)?(x):(y))

#define uint unsigned int

#define LL long long

#define ull unsigned long long

#define swap(x,y) (x^=y,y^=x,x^=y)

#define abs(x) ((x)<0?-(x):(x))

#define INF 1e9

#define Inc(x,y) ((x+=(y))>=MOD&&(x-=MOD))

#define ten(x) (((x)<<3)+((x)<<1))

#define N 100000

using namespace std;

int n,cnt=0,cnt_=0,a[N+5],f[N+5];

struct Interval

{

    int l,r,v;

    Interval(int x=0,int y=0):l(x),r(y){v=1;}

    inline friend bool operator < (Interval x,Interval y) {return x.r^y.r?x.r<y.r:x.l<y.l;}

    inline friend bool operator == (Interval x,Interval y) {return !(x.l^y.l||x.r^y.r);}

}s[N+5];

class FIO

{

    private:

        #define Fsize 100000

        #define tc() (FinNow==FinEnd&&(FinEnd=(FinNow=Fin)+fread(Fin,1,Fsize,stdin),FinNow==FinEnd)?EOF:*FinNow++)

        #define pc(ch) (FoutSize<Fsize?Fout[FoutSize++]=ch:(fwrite(Fout,1,FoutSize,stdout),Fout[(FoutSize=0)++]=ch))

        int f,FoutSize,OutputTop;char ch,Fin[Fsize],*FinNow,*FinEnd,Fout[Fsize],OutputStack[Fsize];

    public:

        FIO() {FinNow=FinEnd=Fin;}

        inline void read(int &x) {x=0,f=1;while(!isdigit(ch=tc())) f=ch^'-'?1:-1;while(x=ten(x)+(ch&15),isdigit(ch=tc()));x*=f;}

        inline void read_char(char &x) {while(isspace(x=tc()));}

        inline void read_string(string &x) {x="";while(isspace(ch=tc()));while(x+=ch,!isspace(ch=tc())) if(!~ch) return;}

        inline void write(int x) {if(!x) return (void)pc('0');if(x<0) pc('-'),x=-x;while(x) OutputStack[++OutputTop]=x%10+48,x/=10;while(OutputTop) pc(OutputStack[OutputTop]),--OutputTop;}

        inline void write_char(char x) {pc(x);}

        inline void write_string(string x) {register int i,len=x.length();for(i=0;i<len;++i) pc(x[i]);}

        inline void end() {fwrite(Fout,1,FoutSize,stdout);}

}F;

inline int find(int x,int len)//二分出一个最大的res使a[res]<x，实现O(logN)转移

{

    register int l=0,r=len,mid=l+r+1>>1;

    for(;l<r;mid=l+r+1>>1) a[mid]<x?l=mid:r=mid-1;

    return l;

}

int main()

{

    register int i,j,x,y,res,Max=0;

    for(F.read(n),i=1;i<=n;++i) F.read(x),F.read(y),x+y<n&&(s[++cnt_]=Interval(x+1,n-y),0),a[i]=INF;//存储区间，注意将a数组初始化为INF

    for(sort(s+1,s+cnt_+1),i=1;i<=cnt_;++i) cnt&&s[cnt]==s[i]?s[cnt].v=min(s[cnt].v+1,s[cnt].r-s[cnt].l+1):s[++cnt]=s[i];//去重

    for(i=1;i<=cnt;++i) //枚举区间

    {

        for(res=find(s[i].l,Max),j=res+1,f[i]=res+s[i].v;j<=f[i];++j) a[j]=min(a[j],s[i].r);

        Max=max(Max,f[i]);//更新最大值

    }

    return F.write(n-Max),F.end(),0;

}

巴特西

【洛谷2519】[HAOI2011] problem a（动态规划）

动态规划

代码

最新文章

热门文章