首页 > 代码库 > 合唱队形(DP)
合唱队形(DP)
原题传送门
这道题目就是裸的DP题,
我们所需要得到的是一个倒V形的数列
即一个上升子序列与下降子序列的合体。。
所以我们只需要做一遍从1到n的最长上升子序列和从n到1的最长上升子序列即可
时间复杂度O(n^2)
下面贴代码
#include<cstdio> #define MN 101 #define max(a,b) (a)>(b)?(a):(b) using namespace std; int num[MN],ss[MN],xj[MN]; int n,ans; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&num[i]); ss[1]=xj[n]=1; for(int i=2;i<=n;i++) { ss[i]=1; for(int j=1;j<i;j++) if(num[j]<num[i])ss[i]=max(ss[i],ss[j]+1); } for(int i=n-1;i>=1;i--) { xj[i]=1; for(int j=i+1;j<=n;j++) if(num[j]<num[i])xj[i]=max(xj[i],xj[j]+1); } for(int i=1;i<=n;i++)ans=max(ans,ss[i]+xj[i]-1); printf("%d\n",n-ans); return 0; }
合唱队形(DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。