gzhuoj 1013 GoodSequence

潜下心学dp

题意：

现定义一个不下降的序列为好序列，给你一个长为$n$的序列，问最少需要修改几个数可让这个序列变成好序列。

题解：

开始好好学$dp$。

这道题其实就是$LIS$，$dp$搞搞就行。

ps：这里用了两种写法，一种是$O(n^2)$，一种是$O(n\log n)$。

AC代码：

其一：

//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define _for(type,i,a,b) for(type i = (a);i<(b);++i)
#define endl '\n'

const int N=5005;
int dp[N],a[N];
signed main() {
  FIO;
  int n;
  while(cin>>n){
    _for(int,i,0,n)cin>>a[i];
    _for(int,i,0,n)dp[i]=1;
    int ans=1;
    _for(int,i,0,n){
      _for(int,j,0,i){
        if(a[i]>=a[j]){
          dp[i]=max(dp[i],dp[j]+1);
          ans=max(ans,dp[i]);
        }
      }
    }
    cout<<n-ans<<endl;
  }
  return 0;
}

其二：

//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define _for(type,i,a,b) for(type i = (a);i<(b);++i)
#define endl '\n'


const int N=5005;
int dp[N],a[N];
signed main() {
  FIO;
  int n;
  while(cin>>n){
    _for(int,i,1,n+1)cin>>a[i];
    _for(int,i,1,n+1)dp[i]=0;
    dp[1]=a[1];
    int len=1;
    _for(int,i,2,n+1){
      if(a[i]>=dp[len])dp[++len]=a[i];
      else{
        int j=upper_bound(dp,dp+len+1,a[i])-dp;
        dp[j]=a[i];
      }
    }
    cout<<n-len<<endl;
  }
  return 0;
}

• 本文作者： baddog
• 本文链接： https://katoli.github.io/2020/10/26/gzhuoj-1013-GoodSequence/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！