BZOJ 2298: [HAOI2011]problem a 动态规划

2021-09-20 12:34:49

2298: [HAOI2011]problem a

Time Limit: 1 Sec

Memory Limit: 256 MB

题目连接

http://www.lydsy.com/JudgeOnline/problem.php?id=2298

Description

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

Input

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

Output

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

Sample Input

2 0

0 2

2 2

Sample Output

HINT

100%的数据满足： 1≤n≤100000 0≤ai、bi≤n

题意

题解：

转换一下，就是求最多有多少个人满足题意

dp[i]表示前i名最多有多少个人没有说谎

那么dp[i]=max(dp[i],dp[j]+sum[j+1][i])其中sum(j+1](i)表示赞同这个区间的人数

代码：

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <bitset>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 200500

#define mod 1001

#define eps 1e-9

#define pi 3.1415926

int Num;

//const int inf=0x7fffffff;

const ll inf=;

inline ll read()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

//*************************************************************************************

struct node

{

    int l,r;

};

vector<int> Q[maxn];

map<pair<int,int> ,int> H;

int dp[maxn];

int main()

{

    int n=read();

    for(int i=;i<n;i++)

    {

        int x=read(),y=read();

        if(x+y>=n)continue;

        x++,y=n-y;

        if(!H[make_pair(x,y)])Q[y].push_back(x);

        H[make_pair(x,y)]++;

        if(H[make_pair(x,y)]>y-x+)H[make_pair(x,y)]=y-x+;

    }

    for(int i=;i<=n;i++)

    {

        dp[i]=dp[i-];

        for(int j=;j<Q[i].size();j++)

            dp[i]=max(dp[i],dp[Q[i][j]-]+H[make_pair(Q[i][j],i)]);

    }

    printf("%d\n",n-dp[n]);

}

码农公寓