Missile:双状态DP
题目
描写叙述
Long , long ago ,country A invented a missile system to destroy the missiles from their enemy . That system can launch only one missile to destroy multiple missiles if the heights of all the missiles form a non-decrease sequence .
But recently , the scientists found that the system is not strong enough . So they invent another missile system . The new system can launch one single missile to destroy many more enemy missiles . Basically , the system can destroy the missile from near to far . When the system is begun , it chooses one enemy missile to destroy , and then destroys a missile whose height is lower and farther than the first missile . The third missile to destroy is higher and farther than the second missile … the odd missile to destroy is higher and farther than the previous one , and the even missile to destroy is lower and farther than the previous one .
Now , given you a list of the height of missiles from near to far , please find the most missiles that can be destroyed by one missile launched by the new system .
输入
The input contains multiple test cases .
In each test case , first line is an integer n ( 0<n<=1000 ) , which is the number of missiles to destroy . Then follows one line which contains n integers ( <=109 ) , the height of the missiles followed by distance .
The input is terminated by n = 0 .
输出
For each case , print the most missiles that can be destroyed in one line .
例子输入
4
5 3 2 4
3
1 1 1
0
例子输出
3
1
大意:
思路
完整代码:
#include<iostream> using namespace std; int a[1001],b[1001]; int str[1001]; int main() { //freopen("aa.txt","r",stdin); int n,i,j,max2; while(scanf("%d",&n)!=EOF) { if(!n) break; for(i=0;i<n;i++) scanf("%d",&str[i]); for(i=0;i<n;i++) { a[i]=1; //as higher b[i]=0; //as lower } for(i=1;i<n;i++) { int max=1,max1=0; for(j=0;j<i;j++) { if(str[i]>str[j]) { a[i]=b[j]+1; if(a[i]>max) max=a[i]; } if(str[i]<str[j]) { b[i]=a[j]+1; if(b[i]>max1) max1=b[i]; } } b[i]=max1; a[i]=max; } max2=a[0]; for(i=0;i<n;i++) { if(a[i]>max2) max2=a[i]; if(b[i]>max2) max2=b[i]; } cout<<max2<<endl; } }
验证
相关文章
- 域名 WHOIS 查询常见状态及说明
- HTML5代码测试终端与服务器之间的网络速度和状态
- 【计算理论】图灵机 ( 接受状态作用 | 格局 | 图灵机语言 | 图灵机设计复杂性 )
- 【Flutter】Animation 动画 ( Flutter 动画基本流程 | 创建动画控制器 | 创建动画 | 设置值监听器 | 设置状态监听器 | 布局中使用动画值 | 动画运行 )
- 【防止恶意用户注册】-- 手机在网状态 API 的防欺诈应用解析
- 一文带你了解SQL Server数据库状态和文件状态
- MySQL Status Innodb_rows_read 数据库状态作用意思及如何正确
- Linux查看防火墙状态:快速、简单、有效(linux查看防火墙状态)
- 检查Linux 服务器状态检查:保障系统运行(linux服务状态)
- Linux清除旧内核:让系统保持最新状态(linux删除旧的内核)