波動序列
時間限制：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);
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;
}
很不幸，TLE了，算了一下時間復雜度O(n^2)的確過不了，其實我是經過一定的優化的，只不過作用實在小了點····
各種調試一直是TLE，一直到第二天早上，想了一晚上也沒有好的解決辦法，後來看看難度是2，感覺不會是dp的難題，然後突然想到，
了一種簡單的方法，一直找遞增或者遞減序列就行了，記一下這些序列的個數輸出即可，就是說先找遞減序列，找到一個極小值，再找
遞增序列，找到一個極大值，再找遞減的····一直到序列結束，線性的復雜度，絕對沒有問題五分鐘 ，代碼搞定，簡單調試，提交AC！
[cpp]
/*
波動序列
*/
#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[30005];
int main()
{
#if(FLAG)
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
//******程序讀入下一組數據之前先【初始化】變量，數組，容器等！！
int T,n,i,j,num,f=0;
scanf("%d",&T);
while(T--)
{
num=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
if(n==1){cout<<1<<endl;continue;}
i=0;
f=0;
while(1)
{
if(f==0)
for(;i<n-1;i++)
{
if(a[i+1]<a[i])
{
num++;
i++;
f=1;
break;
}
}
else
for(;i<n-1;i++)
{
if(a[i+1]>a[i])
{
num++;
i++;
f=0;
break;
}
}
if(i==n-1)break;
}
cout<<num+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[30005];
int main()
{
#if(FLAG)
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
//******程序讀入下一組數據之前先【初始化】變量，數組，容器等！！
int T,n,i,j,num,f=0;
scanf("%d",&T);
while(T--)
{
num=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
if(n==1){cout<<1<<endl;continue;}
i=0;
f=0;
while(1)
{
if(f==0)
for(;i<n-1;i++)
{
if(a[i+1]<a[i])
{
num++;
i++;
f=1;
break;
}
}
else
for(;i<n-1;i++)
{
if(a[i+1]>a[i])
{
num++;
i++;
f=0;
break;
}
}
if(i==n-1)break;
}
cout<<num+1<<endl;
}
return 0;
}
為什麼比賽的時候沒有想到呢？
1，沒有打好配合，不能喝隊友一起攻破難題，單槍匹馬，勢單力薄。
2，賽場比較緊張，思維不靈活。
3，高估了題意，受平時做題思維定勢的影響。
4，沒有透徹的分析題目的用意錯誤的方法在錯誤的地方產生了錯誤的結果
5，以後堅決改正錯誤。
