NYOJ 370 波动序列 dp 动态规划

波动序列
时间限制：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 <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <map>
#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<n;i++)
        {
            scanf("%d",&a[i]);
        }
        if(n==1){cout<<1<<endl;continue;}

for(i=0;i<n-1;i++)
{
    if(a[i+1]<a[i])break;//这里是一个小的优化，除去了数列前面的递增序列
}                       //保证了需要求的序列的第一个是大数a0 > a2 < a3 > a4.......
t=i;
        f[i].b=1;
        if(t==n-1){cout<<1<<endl;continue;}
        for(i=t+1;i<n;i++)
        {
            maxi=0;

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

                        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*="<<f[j].a<<" j="<<j<<endl;
                        maxi=f[j].a+1;
                        f[i].b=1;
                    }
                    else f[i].b=0;
                }
            }
            f[i].a=maxi;
            if(ma<maxi)ma=maxi;
        }
        cout<<ma+1<<endl;
    }
    return 0;
}

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <map>
#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);
  &n

补充：软件开发 , C++ ,