http://acm.pku.edu.cn/JudgeOnline/problem?id=1887題目太羅嗦了,簡單的說就是求最長下降子序列;
這是一通用題,還有最長上升子序列,都是一樣的解法.
狀態轉移方程:
Max(1)=1;
Max( i )=Max{ Max(j): 1<=j<i && a[i]<a[j] }+1;
二十分鐘AC,下面是源代碼
Source Code
Problem: 1887 User: lnmm
Memory: 372K Time: 78MS
Language: C++ Result: Accepted
Source Code
#include"stdio.h"
void main()
{
int i,j,tempMax;
int nCase=1;
int a[32767];
int totalMax[32767];
int temp;
while(scanf("%d",&temp))
{
if(temp==-1)break;
a[1]=temp;
totalMax[1]=1;
for(i=1;;)
{
scanf("%d",&temp);
if(temp==-1)break;
else
{
a[++i]=temp;
tempMax=0; //找到i之前 的totalMax[j]最大且a[j]>a[i]的j值
for(j=1;j<i;j++)
if(a[i]<a[j]&&tempMax<totalMax[j])tempMax=totalMax[j];
totalMax[i]=tempMax+1; //i取的是上面得到的值,加上本身(因為有a[j]>a[i]),所以+1
}
}
temp=0;
for(j=1;j<=i;j++)
if(totalMax[j]>temp)temp=totalMax[j];
printf("Test #%d:\n",nCase++);
printf(" maximum possible interceptions: %d\n\n",temp);
}
}