NYOJ 370 波动序列 dp 动态规划 - c++编程基础

波动序列
时间限制：1000 ms | 内存限制：65535 KB
难度：2
描述
有一个长度为N的整数序列，序列里面的数是两两不同的，现在要在里面找一个波动序列，这个序列越长越好。

比如有波动序列{a0,a1,a2…an-1},则a0 > a1 < a2 > a3 < …

输入
第一行输入一个数T，代表有T个任务,T不大于50。
对于每个任务，输入格式为
N a0 a1 a2 … aN-1
其中N<=30000，测试数据保证序列的数两两不同。
输出
对于每个任务，输出最长的波动序列长度
样例输入
4
5 1 2 3 4 5
5 5 4 3 2 1
5 5 1 4 2 3
5 2 4 1 3 5样例输出
1
2
5
3

说起来这是一道让我纠结了半个下午加一个晚上的题，当时在打比赛，练习赛，当我第一眼看到他的时候也没有看清题，因为当时队友在做我还以为是矩阵什的的题呢（因为看起来四四方方的）我矩阵这块儿不怎么的，就去做别的题了，后来队友做了做思路卡了——也没有跟我们商量就也去看别的题了~~￥##后来我见这题还没有出，看了看，读题后第一感觉是dp问题，只不过是加了条件的dp，有地小复杂，但是可以做。整理思路，打代码，调试一气呵成（其实调试的时候遇到很多问题的·····）
代码如下：（带标记的dp写的，过不了）

[cpp] view plaincopyprint
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define FLAG 0
using namespace std;
int a[30000+5];
struct st
{
int a,b;
}f[30000+5];
int main()
{
#if(FLAG)
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
//******程序读入下一组数据之前先【初始化】变量，数组，容器等！！
int T,n,i,j,maxi,ma,ma2,ff,t;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
ma=1<<31;
memset(f,0,sizeof(f));
for(i=0;i {
scanf("%d",&a[i]);
}
if(n==1){cout<<1<
for(i=0;i {
if(a[i+1] } //保证了需要求的序列的第一个是大数a0 > a2 < a3 > a4.......
t=i;
f[i].b=1;
if(t==n-1){cout<<1< for(i=t+1;i {
maxi=0;

for(j=t;j {
if(f[j].b==1)//大
{
if(a[i] {

maxi=f[j].a+1;
f[i].b=0;
}
else f[i].b=1;
}

else//小
{
if(a[i]>a[j]&&maxi<=f[j].a+1)
{//cout<<"fg*="<

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define FLAG 0
using namespace std;
int a[30000+5];
struct st
{
int a,b;
}f[30000+5];
int main()
{
#if(FLAG)
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
//******程序读入下一组数据之前先【初始化】变量，数组，容器等！！
int T,n,i,j,maxi,ma,ma2,ff,t;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
ma=1<<31;
memset(f,0,sizeof(f));
for(i=0;i {
scanf("%d",&a[i]);
}
if(n==1){cout<<1<

for(i=0;i {
if(a[i+1] } //保证了需要求的序列的第一个是大数a0 > a2 < a3 > a4.......
t=i;
f[i].b=1;
if(t==n-1){cout<<1< for(i=t+1;i {
maxi=0;

NYOJ 370 波动序列 dp 动态规划 (一)