博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
CodeVS 1058 合唱队形(DP--最长子序列问题)
阅读量:6900 次
发布时间:2019-06-27

本文共 903 字,大约阅读时间需要 3 分钟。

题目大意:

求每一个点的之前的最长上升子序列和每一个点的之后的最长下降子序列。

之前报错,因为需要将每一个dp的值赋值为1.

代码:

#include 
#include
using namespace std;int arr[1000] = {
0};int n;int main(){ cin >> n; for(int i = 0; i < n; i++) { cin >> arr[i]; } int dp[1000],dp1[1000]; for(int i = 0; i < 1000; i++) dp[i] = dp1[i] = 1; for(int i = 1 ; i < n; i++) { for(int j = 0; j < i; j++) { if(arr[i] > arr[j]) dp[i] = max(dp[i],dp[j]+1); } } for(int i = n - 2 ; i >= 0; i--) { for(int j = i + 1; j < n; j++) { if(arr[i] > arr[j]) dp1[i] = max(dp1[i],dp1[j]+1); } } int max = 0; for(int i = 0; i < n; i++) { if(dp[i]+dp1[i]-1 > max) max = dp[i]+dp1[i]-1; } cout << n - max << endl; return 0;}

 

转载于:https://www.cnblogs.com/zyqBlog/p/7644237.html

你可能感兴趣的文章
使用 Spring Cloud 搭建微服务项目架构
查看>>
20150910信院研究生新生入学教育
查看>>
JAVAEE Velocity配置例子
查看>>
keepalive配置好启动后无法显示vip
查看>>
Java IO学习笔记:字符流
查看>>
PHP中exit()与die()的区别
查看>>
android--------微信 Tinker 热修复 (一)
查看>>
Android 开发之 布局控件的各个属性
查看>>
实现table、列表隔行换色
查看>>
Mysql 1418 - This function has none of DETERMINISTIC
查看>>
JavaScript 03 - 输出
查看>>
RN 高阶组件,有状态组件,无状态组件,以及组件之间的交互
查看>>
QuickText for Notepad++
查看>>
ASP.NET中IsPostBack详解
查看>>
JDBC--BLOB
查看>>
【Qt笔记】信号槽
查看>>
JAVA中如何去除字符串前后的全角空格(当中保留)(轉)
查看>>
微信小程序常见错误及基本排除方法
查看>>
docker简介
查看>>
iOS 7 交互界面设计总结
查看>>