POJ-1836 Alignment---LIS
2024-09-02 01:43:05
题目链接:
https://cn.vjudge.net/problem/POJ-1836
题目大意:
题意:令到原队列的最少士兵出列后,使得新队列任意一个士兵都能看到左边或者右边的无穷远处。就是使新队列呈三角形分布就对了。
解题思路:
求出每一位结束的最长上升子序列和每一位开始的最长下降子序列,求出最大值,然后用队伍长度减去即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<sstream>
using namespace std;
typedef long long ll;
int dp1[], dp2[];
double a[];
int main()
{
int n;
cin >> n;
for(int i = ; i <= n; i++)cin >> a[i], dp1[i] = , dp2[i] = ;
for(int i = ; i <= n; i++)
{
for(int j = ; j < i; j++)
if(a[i]>a[j])dp1[i] = max(dp1[i], dp1[j] + );
}
for(int i = n; i >= ; i--)
{
for(int j = n; j > i; j--)
if(a[i]>a[j])dp2[i] = max(dp2[i], dp2[j] + );
}
int ans = ;
for(int i = ; i <= n; i++)
for(int j = i + ; j <= n; j++)
ans = max(dp1[i] + dp2[j], ans);
cout<<n - ans<<endl;
}
最新文章
- css3相册图片3D旋转展示特效
- hibernate缓存
- 关于Kendo的Grid 单元格样式
- sublime text2 打开包含中文的文件会自动追加.dump后缀解决办法
- meeting room I &; II
- HTML5学习之视频与音频(三)
- 更新Delphi中SVN客户端版本的方法
- jQuery 关于 end() 方法的详细解释
- 浅谈w3c标准
- python的一些总结1
- (转)Qt Model/View 学习笔记 (三)——Model类
- jquery-ui-datepicker定制化,汉化,因手机布局美观化源码修改
- How to handle the DbEntityValidationException in C#
- 实现C++模板类头文件和实现文件分离的方法
- 【转载】C代码优化方案
- A Typical Homework(学生信息管理系统)
- mysql之连接localhost与127.0.0.1的区别
- Winform DevExpress控件库(一) DevExpress控件库的安装与新建第一个DevExpress项目
- Windows 使用 Visual Studio 编译 caffe
- Luogu3579 Solar Panels