洛谷P1410 子序列 題解 動态規劃

題目連結：​​https://www.luogu.com.cn/problem/P1410​​

題目大意：

給定一個長度為N（N為偶數）的序列，問能否将其劃分為兩個長度為N/2的嚴格遞增子序列。

解題思路：

定義 \(f_{i,j}\) 表示前 \(i\) 個數，\(a_i\) 所在的子序列長度為 \(j\) 的情況下，另外一個子序列的最後一個元素的最小值。

初始時 \(f_{1,1} = 0\)，其他狀态設為 \(inf\)。

最終隻需要判斷 \(f_{n,n/2}\) 是否為 \(inf\) 即可。

if (a[i-1] < a[i]) f[i][j] = min(f[i][j], f[i-1][j-1]);
if (f[i-1][i-j] < a[i]) f[i][j] = min(f[i][j], a[i-1]);      

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2002;
int n, a[maxn], f[maxn][maxn];
int main() {
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; i ++) scanf("%d", a+i);
        memset(f, 0x3f, sizeof(f));
        f[1][1] = 0;
        for (int i = 2; i <= n; i ++) {
            for (int j = 1; j <= i && j <= n/2; j ++) {
                if (a[i-1] < a[i]) f[i][j] = min(f[i][j], f[i-1][j-1]);
                if (f[i-1][i-j] < a[i]) f[i][j] = min(f[i][j], a[i-1]);
            }
        }
        puts( f[n][n/2] == 0x3f3f3f3f ? "No!" : "Yes!" );
    }
    return 0;
}