题解 P4728 [HNOI2009]双递增序列
Ryo_Yamada
·
·
题解
这题“思维难度极高，代码难度极低”。
这题的状态定义非常神仙，用我们老师的话来说就是转移的艺术qaq。
对于枚举过的前 i 个元素，若分成 2 个子序列，必定有一个子序列的末尾是 A_i。所以首先可以想到，对于 dp_i，表示前 i 个元素已经枚举，有一个子序列的末尾是 A_i。
当然这些不够，再加一维：对于 dp_{i,j}，表示表示前 i 个元素已经枚举，有一个子序列的末尾是 A_i，其中不包含 A_i 的子序列长度为 j ，则包含 A_i 的子序列长度为 i-j，用 dp_{i,j} 表示该子序列末尾的最小值。
这样，我们就用两维的状态表示出了四个信息，最终答案是 dp_{n, \frac{n}{2}}。
再考虑转移：
最后，dp 数组初始值全部设为 +\infty，dp_{1,1}=-\infty，时间复杂度 O(n^2)。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 2005;
int T, n;
int a[N], dp[N][N];
int main() {
cin >> T;
while(T--) {
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", a + i);
memset(dp, 0x3f, sizeof dp);
dp[1][1] = -inf;
for(int i = 1; i < n; i++) {//由于我的转移是转移i+1，所以i<n。
for(int j = 1; j <= min(n / 2, i); j++) {//剪去无用状态
if(a[i] < a[i + 1]) dp[i + 1][j + 1] = min(dp[i][j], dp[i + 1][j + 1]);
if(a[i + 1] > dp[i][j]) dp[i + 1][i - j + 1] = min(a[i], dp[i + 1][i - j + 1]);//转移
}
}
if(dp[n][n / 2] == inf) puts("No!");
else puts("Yes!");
}
return 0;
}
```