/ Vijos / 讨论 / 花匠 /

AC程序求神犇科学一点的证明。。。。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100010;
int n,i,tot,ans,q[N],h[N];

int main()
{
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d",&h[i]);
memset(q,0,sizeof(q));
tot=1;
q[1]=h[1];
for (i=1;i<=n;i++)
{
if (tot&1)
{
if (q[tot]<h[i]) q[++tot]=h[i];
else q[tot]=h[i];
}
else
{
if (q[tot]>h[i]) q[++tot]=h[i];
else q[tot]=h[i];
}
}
ans=tot;
memset(q,0,sizeof(q));
tot=1;
q[1]=h[1];
for (i=1;i<=n;i++)
{
if (tot&1)
{
if (q[tot]>h[i]) q[++tot]=h[i];
else q[tot]=h[i];
}
else
{
if (q[tot]<h[i]) q[++tot]=h[i];
else q[tot]=h[i];
}
}
ans=max(ans,tot);
printf("%d\n",ans);
return 0;
}

2 条评论

  • @ 2015-01-23 20:39:53

    数学优化 求节点数即可 节点:不是最后和第一个花 且满足比两边都大或都小
    没有节点输出一
    用滚动数组三个数中间数与两边边比较

  • @ 2013-11-12 10:32:32

    代码太乱,Markdown自带语法高亮,可以用一下。

    简化题目的意思就是使得处理完的序列中**连续上升/下降**的序列长度不超过2。按照这个原则对原序列进行修改就行了,扫一遍即可。

    • @ 2013-11-13 08:36:25

      贴上来就变这样了。。。

  • 1

信息

ID
1845
难度
6
分类
(无)
标签
递交数
4343
已通过
1237
通过率
28%
被复制
9
上传者