洛谷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$
3

刪除掉原數列的其中一個 $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要再練了…