洛谷P1799 數列

題目連結: https://www.luogu.com.cn/problem/P1799
題目大意:
給定一個數列 $A_n$，
你現在可以做下列操作任意次數(也可 $0$ 次):

從這個數列刪除一個元素，剩下的元素依照相對位置不變靠攏。

令新的數列為 $B_k$，請問$B_i=i$的位置最多能有多少個。

$n\leq 1000$
$A_i\leq 10^9$

Sample

$Sample$ $Input$

5
1 1 2 5 4

$Sample$ $Output$

刪除掉原數列的其中一個 $1$，使數列變成$1,2,5,4$，其中 $1,2,4$ 符合 $B_i=i$。

Solution

考慮 $Dynamic$ $programming$。
令 $dp[i][j]$ 為前 $i$ 個數字刪除 $j$ 個數後，$B_i=i$ 的最多個數。

轉移式如下:

如果要刪除第 $i$ 個數，則 $dp[i][j]={max(dp[k][j-1])| 1\leq k<i }$
如果不刪除第 $i$ 個數，則 $dp[i][j]={max(dp[k][j]+[A_{i}=(i-j)]| 1\leq k<i }$

所以 $dp[i][j]$ 即為上面兩種中的最大值。
所求就是 ${max(dp[n][i])| 1\leq i\leq n }$

Code

#include <bits/stdc++.h>
#define int long long
#define SpeedUP ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int n;
int a[1005];
int dp[1005][1005]; //dp[i][j]表第1~i個數已經有j個數刪除
void sol(){
    cin >>n;
    for (int i=1;i<=n;i++) cin >>a[i];
    dp[1][0]=(a[1]==1);dp[1][1]=0;
    for (int i=2;i<=n;i++){
        for (int j=0;j<=i;j++){
            int mx1=0,mx2=0;
            for (int k=j;k<i;k++) mx1=max(mx1,dp[k][j]);
            for (int k=j;k<i;k++) mx2=max(mx2,dp[k][j-1]);
            dp[i][j]=max(mx1+(a[i]==(i-j)),mx2);
        }
    }
    int ans=0;
    for (int i=1;i<=n;i++) ans=max(ans,dp[n][i]);
    cout <<ans;
}
signed main(){
    SpeedUP
    int tEst=1;
    //cin >>tEst;
    while (tEst--) sol();
    return 0;
}

時間複雜度: $O(n^3)$。
看起來會吞 $TLE$，可是卻能 $AC$ ???
原因很簡單，因為在洛谷的評測業面有一個神奇小勾勾。

神奇小勾勾勾下去後，就能加速 $AC$ 了~~

Solution-2

但不是每個網站都有神奇小勾勾，是說可以砸一個資料結構讓複雜度變 $O(n^2logn)$。
但我懶的寫 $0u0$。
這邊說一個 $O(n^2)$ 的算法。
其實就是上面的方法拔掉最後一個迴圈…

Code-2

#include <bits/stdc++.h>
#define int long long
#define SpeedUP ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int n;
int a[1005];
int dp[1005][1005]; //dp[i][j]表第1~i個數已經有j個數刪除
void sol(){
    cin >>n;
    for (int i=1;i<=n;i++) {
        cin >>a[i];
        assert(a[i]<=1000000000);
    }
    dp[1][0]=(a[1]==1);dp[1][1]=0;
    for (int i=2;i<=n;i++){
        for (int j=0;j<=i;j++){
            dp[i][j]=max(dp[i-1][j-1],dp[i-1][j]+(a[i]==(i-j)));
        }
    }
    int ans=0;
    for (int i=1;i<=n;i++) ans=max(ans,dp[n][i]);
    cout <<ans;
}
signed main(){
    SpeedUP
    int tEst=1;
    //cin >>tEst;
    while (tEst--) sol();
    return 0;
}

時間複雜度: $O(n^2)$。
其實狀態轉移 $dp[i][j]=max(dp[i-1][j-1],dp[i-1][j]+[A_i=i-j])$ 就好…
我弱，只會 $O(n^3)$+小勾勾…，Dp要再練了…