hdu_5773_The All-purpose Zero(LIS)

题意：

给你一串数，让你求LIS，不过这里的0可以改变为任意数

题解：

官方题解讲的很清楚

1010 The All-purpose Zero

0可以转化成任意整数，包括负数，显然求LIS时尽量把0都放进去必定是正确的。因此我们可以把0拿出来，对剩下的做O(nlogn)的LIS，统计结果的时候再算上0的数量。为了保证严格递增，我们可以将每个权值S[i]减去i前面0的个数，再做LIS，就能保证结果是严格递增的。

 #include<bits/stdc++.h>

 #define F(i,a,b) for(int i=a;i<=b;++i)

 using namespace std;

 const int N=1e5+;

 int a[N],b[N];

 int main(){

     int t,n,tp,ic=;

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d",&n);

         int cnt=,ed=,len;

         F(i,,n)

         {

             scanf("%d",&tp);

             if(tp)a[++ed]=tp-cnt;else cnt++;

         }

         if(!ed)printf("Case #%d: %d\n",ic++,n);

         else{

             b[len=]=a[];

             F(i,,ed)if(a[i]>b[len])b[++len]=a[i];

             else b[lower_bound(b+,b++len,a[i])-b]=a[i];

             printf("Case #%d: %d\n",ic++,len+cnt);

         }

     }

     return ;

 }

巴特西

hdu_5773_The All-purpose Zero(LIS)

1010 The All-purpose Zero

最新文章

热门文章