首页 > 代码库 > 最长上升子序列——蒜头君的娃娃
最长上升子序列——蒜头君的娃娃
蒜头君十分喜爱它的娃娃,经常会把它们摆成一列。蒜头君从左到右依次给他们编号为 11 到 NN,每个娃娃都有自己的萌值 T_iT?i??。现在蒜头君想从已经摆好的队列中,去除几个娃娃,使得剩余的队列满足以下条件:
\displaystyle T_1 < ... < T_i > T_{i+1} > ... > T_K (1 \leq i \leq K)T?1??<...<T?i??>T?i+1??>...>T?K??(1≤i≤K)
现在已知队列中 NN 个娃娃的萌值,请你帮蒜头君计算一下,最少需要去除多少个娃娃才能满足上面的条件。
输入格式
输入两行。输入第一行是一个整数 N(2 \leq N \leq 100)N(2≤N≤100),表示娃娃的总数。第二行输入 NN 个整数,每两个整数之间用一个空格隔开,第 ii 个整数 T_i(130 \leq T_i \leq 230)T?i??(130≤T?i??≤230) 是第 ii 个娃娃的萌值。
输出格式
输出一行,输出一个整数,表示最少去除娃娃的个数。
样例输入
6 184 163 210 166 170 155
样例输出
2
分析:正向dp一次,反向dp一次,然后取两次dp值的和中最大的那个。答案即为娃娃的总数减去最大和值+1。O(n^2)算法
AC代码
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 int n;//娃娃总数 5 int a[105];//存储娃娃萌值 6 int dp1[105];//存储正向dp结果 7 int dp2[105];//存储反向dp结果 8 void DP1()//正向dp 9 { 10 for(int i=1;i<=n;i++) 11 for(int j=1;j<i;j++) 12 { 13 if(a[i]>a[j]) 14 dp1[i]=max(dp1[i],dp1[j]+1); 15 } 16 17 } 18 void DP2()//反向dp 19 { 20 for(int i=n;i>=1;i--) 21 for(int j=n;j>i;j--) 22 { 23 if(a[i]>a[j]) 24 dp2[i]=max(dp2[i],dp2[j]+1); 25 } 26 27 } 28 int get_ans() 29 { 30 int ans=0; 31 for(int i=1;i<=n;i++) 32 { 33 ans=max(ans,dp1[i]+dp2[i]); 34 } 35 return ans; 36 } 37 int main() 38 { 39 scanf("%d",&n); 40 for(int i=1;i<=n;i++) 41 { 42 scanf("%d",&a[i]); 43 dp1[i]=1; 44 dp2[i]=1; 45 } 46 DP1(); 47 DP2(); 48 int ans=get_ans(); 49 printf("%d\n",n-ans+1); 50 return 0; 51 }
最长上升子序列——蒜头君的娃娃
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。