这个题其实很简单。但是因为题目描述没懂,wa了很多次。
建议各个noip选手,请你们一定多敲一些代码,少用一些模板。这样对你们的思路很有帮助,哪怕不是为了获奖,做题的思路对你以后的帮助还是很大的。
这个题目有点坑
这个题目让这一帮人,先上去,再下来。所以从前面找一次上升子序列,再从后面找一次上升子序列就可以了。
但是切记,不要从前面找下降的子序列。(可以自己画一下,你就明白了。或者输出一下找完的过程。)
C++ 代码
/*****************************************
Problem Name :
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e5 + 10;
int a[N];
int dpl[N];
int dpr[N];
int main()
{
int n ;
cin >> n;
for(int i = 1 ; i <= n ; i++)
{ // 需要找 一个中间值,取到两边的和最大值
cin >> a[i];
dpl[i] = 1;
for(int j = i-1 ; j >= 1 ;j--)
{
if(a[i] < a[j])
dpl[i] = max(dpl[i] , dpl[j] + 1);
}
}
for(int i = n ; i >= 1 ;i--)
{
dpr[i] = 1;
for(int j = i+1 ; j <= n ; j++ )
{
if(a[i] < a[j])
dpr[i] = max(dpr[i] , dpr[j] + 1);
}
}
int maxx = 0;
for(int i = 1 ; i <= n ; i++)
maxx = max(maxx , dpr[i] + dpl[i] -1);
cout << maxx << endl;
}
需要这么多头文件吗??
“但是切记,不要从前面找下降的子序列。(可以自己画一下,你就明白了。或者输出一下找完的过程。)”
这个是为什么呀,我确实从前面找的最长下降子序列,就WA了
这么说吧, 因为你是从前往后枚举的下降子序列当i = 1的时候, 你会枚举后面的数字吗? 显然不会
大佬,能细说一下吗,看不太懂