动态规划--合唱队形

动态规划--合唱队形

题目大概：

一行数字要求从两边到中间依次增大，问给出的一行数字要去掉多少才能形成这种数列。

思路：

可以任选一个做中间数k，从1到n。

然后求第一个数到k的最长上升子序列的长度la，再求最后一个数到k的最长上升子序列的长度lb。

最后n-（la+la-1）就是去掉的数字个数，减一是因为多算了一个k。

感想：

有些题需要几个简单的算法混合使用或者重复使用。

代码：

#include using namespace std;int main(){int n,thm=300;int a[1001]={0},b[1001]={0},dp[1001]={0},c[1001]={0};b[1]=1;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int y=1;y<=n;y++){int ma=0;for(int i=2;i<=y;i++){ma=0;for(int t=1;ta[t]){if(b[t]>ma){ma=b[t];}} } b[i]=ma+1;}c[n]=1;for(int i=n-1;i>=y;i--){ma=0;for(int t=n;t>i;t--){if(a[i]>a[t]){if(c[t]>ma){ma=c[t];}} } c[i]=ma+1;}dp[y]=n-b[y]-c[y]+1;if(thm>dp[y])thm=dp[y];}cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。