题解 P6564 【[POI2007] 堆积木KLO】

syf2008 · 2020-06-29 22:02:42 · 题解

这道题我看题解的各位大佬用了dp,本蒟蒻来一发结构体

这题最难的就是思想

1. 首先你得知道这题要用upper_bound
2. 你如果像我用结构体，那你一定要会用sort结构体排序或者你也可以用题解的dalao用树状数组

上代码

#include <bits/stdc++.h>
using namespace std;
struct ss
{
    int a,i;
}b[100005];//建立结构体
int zhuan(ss a,ss b)//sort要用
{
    if(b.a==a.a)
    return b.i<a.i;
    return b.a>a.a;
}
int d[100005],ss,s=0,n,maxn=1;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {cin>>ss;//输入
    if(ss<=i)//如果它的值小于编号，如果值大于编号，是不可能有价值，屏蔽
    {b[++s].a=ss;
    b[s].i=i-ss;}//i-ss是求他到有价值的差}
    if(!s)//如果没有一个可能有价值
    {cout<<0<<endl;return 0;}
    sort(b+1,b+s+1,zhuan);
    d[1]=b[1].i;
    for(int i=2;i<=s;i++)
    {
    int v=upper_bound(d+1,d+maxn+1,b[i].i)-d;//二分查找
    d[v]=b[i].i;
    maxn=max(v,maxn);//比对
    }
    cout<<maxn<<endl;
}