Problem 1 子序列(subsequence.pas/c/cpp) 【題目描述】 給定一個長度為N（N為偶數）的序列，問能否將其劃分為兩個長度為N/2的嚴格遞增子序列， 【輸入格式】 若干行，每行表示一組數據。對於每組數據，首先輸入一個整數N，表示序列的長度。之後N個整數表示這個序列。 【輸出格式】 同輸入行數。對於每組數據，如果存在一種劃分，則輸出“Yes!”，否則輸出“No!“。 【樣例輸入】 6 3 1 4 5 8 7 6 3 2 1 6 5 4 【樣例輸出】 Yes! No! 【數據范圍】 共三組數據，每組數據行數<=50，0 <= 輸入的所有數 <= 10^9 第一組(30%)：N <= 20 第二組(30%)：N <= 100 第三組(40%)：N <= 2000 一般青年Dp方案：F[i][j][k][l] 表示前i+j位分為一個長度為i以j結尾，一個長度為k以l結尾的序列 是否可行(0,1) 省略已知值：觀察發現j和l中至少有一個為a[i+j] 故可省略其中一位 n=2000必跪 文藝青年Dp方案： 挪位得解：把f[i][j][k]中的k挪出來 原因：顯然i和j不變時，我們希望k越小越好 所以記錄min(k)，並記錄無解情況 O(n^2) [cpp] #include<cstdio> #include<iostream> #include<algorithm> #include<functional> #include<cstdlib> #include<cstring> #include<cmath> using namespace std; #define MAXN (2000+10) #define INF (2139062143) int n,a[MAXN],f[MAXN][MAXN]; int main() { freopen("subsequence.in","r",stdin); freopen("subsequence.out","w",stdout); while (scanf("%d",&n)!=EOF) { memset(f,127,sizeof(f)); for (int i=1;i<=n;i++) scanf("%d",&a[i]); f[1][1]=-1; for (int i=1;i<n;i++) { for (int j=1;j<=i;j++) { if (f[i][j]!=INF) { if (a[i]<a[i+1]) f[i+1][j+1]=min(f[i+1][j+1],f[i][j]); if (f[i][j]<a[i+1]) f[i+1][i-j+1]=min(f[i+1][i-j+1],a[i]); } } } /* for (int i=0;i<=n;i++) { for (int j=0;j<=n;j++) printf("%d ",f[i][j]); printf("\n"); } */ if (f[n][n>>1]!=INF) printf("Yes!\n"); else printf("No!\n"); } return 0; }
