子序列(省略已知值法与挪位得解法)
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;
}
补充:软件开发 , C++ ,