BZOJ 1489: [HNOI2009]双递增序( dp )

dp(i, j)表示选第i个, 且当前序列长度为j, 另一个序列的最后一个元素的最小值...然后根据上一个是哪个序列选的讨论一下就行了...奇怪的dp...

-------------------------------------------------------------

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

const int INF = 0X3F3F3F3F;

const int maxn = 2009;

int dp[maxn][maxn], seq[maxn], N;

int main() {

int T;

scanf("%d", &T);

while(T--) {

scanf("%d", &N);

for(int i = 1; i <= N; i++) scanf("%d", seq + i);

seq[0] = -1;

memset(dp, INF, sizeof dp);

dp[0][0] = -1;

for(int i = 1; i <= N; i++)

for(int j = 0; j <= i; j++) {

if(dp[i - 1][i - j] < seq[i]) dp[i][j] = seq[i - 1];

if(seq[i - 1] < seq[i]) 

dp[i][j] = min(dp[i][j], dp[i - 1][j]);

}

puts(dp[N][N / 2] != INF ? "Yes!" : "No!");

}

return 0;

}

-------------------------------------------------------------