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

f[i].a=maxi;
if(ma }
cout< }
return 0;
}

很不幸，TLE了，算了一下时间复杂度O(n^2)的确过不了，其实我是经过一定的优化的，只不过作用实在小了点····
各种调试一直是TLE，一直到第二天早上，想了一晚上也没有好的解决办法，后来看看难度是2，感觉不会是dp的难题，然后突然想到，
了一种简单的方法，一直找递增或者递减序列就行了，记一下这些序列的个数输出即可，就是说先找递减序列，找到一个极小值，再找
递增序列，找到一个极大值，再找递减的····一直到序列结束，线性的复杂度，绝对没有问题五分钟，代码搞定，简单调试，提交AC！

[cpp]
/*

波动序列

*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#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 {
scanf("%d",&a[i]);
}
if(n==1){cout<<1< i=0;
f=0;
while(1)
{
if(f==0)
for(;i {
if(a[i+1] {
num++;
i++;
f=1;
break;
}
}
else
for(;i {
if(a[i+1]>a[i])
{
num++;
i++;
f=0;
break;
}
}
if(i==n-1)break;
}

cout<

}

return 0;
}

波动序列

*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#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 {
scanf("%d",&a[i]);
}
if(n==1){cout<<1< i=0;
f=0;
while(1)
{
if(f==0)
for(;i {
if(a[i+1] {
num++;
i++;
f=1;
break;
}
}
else
for(;i {
if(a[i+1]>a[i])
{
num++;
i++;
f=0;
break;
}
}
if(i==n-1)break;
}

cout<

}

return 0;
}

为什么比赛的时候没有想到呢？
1，没有打好配合，不能喝队友一起攻破难题，单枪匹马，势单力薄。
2，赛场比较紧张，思维不灵活。
3，高估了题意，受平时做题思维定势的影响。
4，没有透彻的分析题目的用意错误的方法在错误的地方产生了错误的结果
5，以后坚决改正错误。

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