ZZNU 1719（最长上升子序列+最长下降子序列）

先吐血一发，噗！

再吐血一次，啊啊啊啊！

好吧，做了那么多次最长上升子序列，看这题看了半天才发现还有最长下降子序列，呵呵哒！

AC代码：

#include<stdio.h>//老恶心
#include<cmath>
#include<string.h>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;

int a[30000],dp[30000],dp2[30000];

int main()
{
int maxn=1,n=0,minn=1;
while(cin>>a[++n])
{
dp[n]=dp2[n]=1;
}
n--;
for(int i=2; i<=n; i++)
{
for(int j=1; j<i; j++)
{
if(a[i]>a[j])
{
dp[i]=max(dp[i],dp[j]+1);
}
else
dp2[i]=max(dp2[i],dp2[j]+1);
}
maxn=max(dp[i],maxn);
minn=max(dp2[i],minn);
}
printf("%d\n%d\n",minn,maxn);

return 0;
}

巴特西

ZZNU 1719（最长上升子序列+最长下降子序列）

最新文章

热门文章