作者在 2011-01-09 20:49:53 发布以下内容
子数列（子数列（双向dp））
Description
现在有一个数列，需要你求得该数列满足下述要求的最长子数列。子数列要求：这个子数列可以被分成前后两个部分，且两部分共同拥有一个数列项（即前一部分的最后一个数列项和后一部分的第一个数列项是同一个数列项）；子数列的前一部分各项要严格递增，后一部分各项要严格递减。例如，数列 1 4 6 5 2 1 可以分成 1 4 6 和 6 5 2 1 这两部分。他们都含有数列项 6 ，且前者各项严格递增，后者各项严格递减。
请你编写程序回答，对一个数列最少剔除几项，就可使剩下的各项组成的子数列满足上述的要求。
Input
输入数据有若干组。每组的第一行为整数 n (1 <= n <= 50) 表示数列的项数，第二行的 n 个整数即为该数列的各项，范围 1 到 1000000000 。
Output
输出最少需要剔除数列中的几项。一个结果一行。
Sample Input
6
1 4 6 5 2 1
5
2 2 2 2 2
Sample Output
0
4
//b[i]表示b[1..i]的最长升序列，前向dp
//c[i]表示c[n..i]的最长升序列，后向dp
//b[i]+c[i] - 1的意义应该很明确了，它就是满足条件的最长子序列的长度
#include <iostream>
using namespace std;
int a[51],b[51],c[51],n;
void dp()
{
int i,j,max;
for(i=1;i<=n;i++)
b[i]=c[i]=1;
for(i=2;i<=n;i++)
{
for(j=1;j<i;j++)
{
if(a[j]<a[i]&&b[i]<=b[j])
b[i]++;
}
}
for(i=n-1;i>=1;i--)
{
for(j=n;j>i;j--)
{
if(a[j]<a[i]&&c[i]<=c[j])
c[i]++;
}
}
max=b[1]+c[1];
for(i=2;i<=n;i++)
if(b[i]+c[i]>max)
max=b[i]+c[i];
printf("%d\n",n-(max-1));
}
int main()
{
int i;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
dp();
}
return 0;
}
//c[i]表示c[n..i]的最长升序列，后向dp
//b[i]+c[i] - 1的意义应该很明确了，它就是满足条件的最长子序列的长度
#include <iostream>
using namespace std;
int a[51],b[51],c[51],n;
void dp()
{
int i,j,max;
for(i=1;i<=n;i++)
b[i]=c[i]=1;
for(i=2;i<=n;i++)
{
for(j=1;j<i;j++)
{
if(a[j]<a[i]&&b[i]<=b[j])
b[i]++;
}
}
for(i=n-1;i>=1;i--)
{
for(j=n;j>i;j--)
{
if(a[j]<a[i]&&c[i]<=c[j])
c[i]++;
}
}
max=b[1]+c[1];
for(i=2;i<=n;i++)
if(b[i]+c[i]>max)
max=b[i]+c[i];
printf("%d\n",n-(max-1));
}
int main()
{
int i;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
dp();
}
return 0;
}