首页 > 代码库 > BZOJ 2298 problem a（DP）

BZOJ 2298 problem a（DP）

2024-07-08 23:44:26   221人阅读

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=2298

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

思路：对于第i个人来说，区间[ai+1,n-bi]的人的分数相同。那么我们用sum[L][R]表示区间[L,R]中总人数。用f[i]表示前i个人中说真话的最大人数，那么f[j]=max(f[i-1]+sum[i][j])。

 

map<pair<int,int > ,int> mp;vector<int> V[N];int n,f[N]; int main(){    RD(n);    int i,x,y,L,R;    FOR1(i,n)    {        RD(x,y);        L=x+1; R=n-y;        if(L>R) continue;        if(mp.count(MP(L,R)))         {            if(mp[MP(L,R)]<R-L+1) mp[MP(L,R)]++;        }        else mp[MP(L,R)]=1,V[R].pb(L);    }    int j;    FOR1(i,n)     {        f[i]=f[i-1];        FOR0(j,SZ(V[i]))        {            L=V[i][j];            upMax(f[i],f[L-1]+mp[MP(L,i)]);        }    }    PR(n-f[n]);}

 

 

 


联系
我们