当前位置:网站首页>最长上升子序列模型 AcWing 482. 合唱队形
最长上升子序列模型 AcWing 482. 合唱队形
2022-07-07 12:08:00 【T_Y_F666】
最长上升子序列模型 AcWing 482. 合唱队形
原题链接
算法标签
DP 线性DP 最长上升子序列
思路
分别求以i结尾上升序列,以i结尾反向上升即下降序列,得到以i为分割点先上升后下降序列,取最大值, 将总数减最大值即可。
代码
#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>=b;--i)
using namespace std;
const int N = 1005, INF = 0x3f3f3f3f;
int f[N], f1[N], a[N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
void put(int x) {
if(x<0) putchar('-'),x=-x;
if(x>=10) put(x/10);
putchar(x%10^48);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n=read();
rep(i, 1, n+1){
a[i]=read();
}
int ans=0, ans1=0, ans2=0;
// 以i结尾上升序列
rep(i, 1, n+1){
f[i]=1;
rep(j, 1, i){
if(a[j]<a[i]){
f[i]=max(f[i], f[j]+1);
}
}
ans1=max(ans1, f[i]);
}
// 以i结尾反向上升即下降序列
Rep(i, n, 0){
f1[i]=1;
Rep(j, n, i+1){
if(a[j]<a[i]){
f1[i]=max(f1[i], f1[j]+1);
}
}
ans2=max(ans2, f1[i]);
}
// 先上升 后下降序列
rep(i, 1, n+1){
ans=max(ans, (f[i]+f1[i]-1));
}
printf("%lld\n", n-ans);
}
与y总代码思路一致
y总代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n;
int h[N];
int f[N], g[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &h[i]);
for (int i = 0; i < n; i ++ )
{
f[i] = 1;
for (int j = 0; j < i; j ++ )
if (h[i] > h[j])
f[i] = max(f[i], f[j] + 1);
}
for (int i = n - 1; i >= 0; i -- )
{
g[i] = 1;
for (int j = n - 1; j > i; j -- )
if (h[i] > h[j])
g[i] = max(g[i], g[j] + 1);
}
int res = 0;
for (int i = 0; i < n; i ++ ) res = max(res, f[i] + g[i] - 1);
printf("%d\n", n - res);
return 0;
}
原创不易
转载请标明出处
如果对你有所帮助 别忘啦点赞支持哈
边栏推荐
- 搜索框效果的实现【每日一题】
- Custom thread pool rejection policy
- Laravel form builder uses
- 现在网上开户安全么?那么网上开户选哪个证券公司?
- "Song of ice and fire" in the eleventh issue of "open source Roundtable" -- how to balance the natural contradiction between open source and security?
- Social responsibility · value co creation, Zhongguancun network security and Information Industry Alliance dialogue, wechat entrepreneur Haitai Fangyuan, chairman Mr. Jiang Haizhou
- 2022-7-7 Leetcode 34. Find the first and last positions of elements in a sorted array
- Excuse me, why is it that there are no consumption messages in redis and they are all piled up in redis? Cerely is used.
- requires php ~7.1 -&gt; your PHP version (7.0.18) does not satisfy that requirement
- 干货|总结那些漏洞工具的联动使用
猜你喜欢
Battle Atlas: 12 scenarios detailing the requirements for container safety construction
作战图鉴:12大场景详述容器安全建设要求
高等數學---第八章多元函數微分學1
交付效率提升52倍,运营效率提升10倍,看《金融云原生技术实践案例汇编》(附下载)
Social responsibility · value co creation, Zhongguancun network security and Information Industry Alliance dialogue, wechat entrepreneur Haitai Fangyuan, chairman Mr. Jiang Haizhou
最佳实践 | 用腾讯云AI意愿核身为电话合规保驾护航
Navicat run SQL file import data incomplete or import failed
干货|总结那些漏洞工具的联动使用
最长上升子序列模型 AcWing 1014. 登山
Details of redis core data structure & new features of redis 6
随机推荐
2022-7-7 Leetcode 844. Compare strings with backspace
Cesium 已知一点经纬度和距离求另一个点的经纬度
PostgreSQL array type, each splice
Solve the cache breakdown problem
requires php ~7.1 -&gt; your PHP version (7.0.18) does not satisfy that requirement
Laravel5 call to undefined function OpenSSL cipher IV length() error php7 failed to open OpenSSL extension
Leetcode simple question sharing (20)
【日常训练】648. 单词替换
Did login metamask
最长上升子序列模型 AcWing 1014. 登山
Attribute keywords aliases, calculated, cardinality, ClientName
Parameter keywords final, flags, internal, mapping keywords internal
[fortress machine] what is the difference between cloud fortress machine and ordinary fortress machine?
Excuse me, when using Flink SQL sink data to Kafka, the execution is successful, but there is no number in Kafka
THINKPHP框架的优秀开源系统推荐
MySQL "invalid use of null value" solution
Learning breakout 2 - about effective learning methods
Help tenants
Co create a collaborative ecosystem of software and hardware: the "Joint submission" of graphcore IPU and Baidu PaddlePaddle appeared in mlperf
. Net core about redis pipeline and transactions