【NOIP】2013 花匠
2024-10-20 15:53:26
【算法】贪心
【题解】
DP可以f[i][0],f[i][1]表示选了i分别满足条件AB的答案,其优化也是利用了下面的性质,不多赘述。
想象数列的波动,最大值一定是取每个波峰和每个波谷,那么只要O(n)统计就可以了。
#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
int read()
{
char c;int s=,t=;
while(!isdigit(c=getchar()))if(c=='-')t=-;
do{s=s*+c-'';}while(isdigit(c=getchar()));
return s*t;
}
/*------------------------------------------------------------*/
const int inf=0x3f3f3f3f,maxn=; int n,a[maxn]; int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d",&a[i]);
bool ok=,flag=;
for(int i=;i<=n;i++)
{
if(a[i]>a[i-]){flag=;ok=;break;}
if(a[i]<a[i-]){flag=;ok=;break;}
}
if(!ok){printf("");return ;}
int ans=;
for(int i=;i<=n;i++)
{
if(flag)
{
if(a[i]<a[i-])
{
flag=;
ans++;
}
}
else
{
if(a[i]>a[i-])
{
flag=;
ans++;
}
}
}
printf("%d",ans+);
return ;
}
最新文章
- 编写高质量代码改善C#程序的157个建议[为泛型指定初始值、使用委托声明、使用Lambda替代方法和匿名方法]
- WebKit渲染基础(转载 学习中。。。)
- Access数据库参数没值
- Atmel Studio 6.0 重新安装
- xrdp远程 &; watchdog 启用与测试 &; WebRTC
- 9.DataPager
- swift——设置navigationitemtitle的内容以及格颜色
- SSH登录与增删改查demo详解+源代码
- 数据库数据对比自动生成sql
- 【Alpha】——First scrum Meeting
- R学习笔记 第二篇:矩阵、数组和列表
- 隐藏index.php
- Caused by: org.h2.jdbc.JdbcSQLException: Table ";T_STUDENT_INFO"; not found; SQL statement
- JS生成 UUID的方法
- git pull 撤销误操作
- application.properties配置文件
- fiddler电脑抓包和手机抓包
- 【转载】JVM系列一:JVM内存组成及分配
- 洛谷 P2629 好消息,坏消息
- iptables-25个常用用法【转】
热门文章
- Gym - 100851F Froggy Ford kruskal
- Java中Collection和Collections的区别(转载)
- HashCode和equals的理解
- iOS- <;项目笔记>; UIApplication常见属性与方法总结
- 数据库集群之路二 MYCAT
- Qt在VS(Visual Studio)中使用
- JVM(二)GC
- Tomcat 7优化配置
- WPF绑定到父元素的属性的方法
- 静态方法不能使用this的原因 当没有实例对象时候 在静态方法里面传入this时会出现空指针异常现象 所以为了防止该现象 静态方法里面不能使用this