您的位置：程序门 -> 专题开发/技术/项目 -> 数据结构与算法

请教一个关于动态规划算法的问题！！谢谢啦！！！！

[收藏此页] [打印本页]选择字色：背景色：字体：[大][中][小]

请教一个关于动态规划算法的问题！！谢谢啦！！！！[已结贴,结贴人:smilesmiling]

发表于：2007-10-16 20:12:06 楼主

题目：
n位同学站成一排，音乐老师要请其中的（n-k)位同学出列，使得剩下的k位同学排成合唱队形。

合唱队形是指这样的一种队形：设k位同学从左到右依次编号为1，2…，k，他们的身高分别为t1，t2，…，tk，则他们的身高满足t1 < t2 < ... < ti > ti+1 > … > tk（1 <=i <=k)。

你的任务是，已知所有n位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

请各位高手给去具体算法，小女子感激不尽啦！！谢谢！！

发表于：2007-10-16 21:15:501楼得分:0

该问题即最长递增子序列的问题，lz可以google一下，存在一个nlogn的算法

发表于：2007-10-19 02:28:262楼得分:0

楼上说的很对！
原文题等价于求解
s（1,n)=max{c（1,i-1)+d（i+1,n)+1} s.t.1 <=i <=n
其中前者即为求最长递减子序列，后者即为求最长递增子序列；最后再作一个优化。

发表于：2007-10-19 19:19:483楼得分:20

acmer? 最讨厌动态规划，脑子笨，总想不出来子状态，不过这个题偶还是会的，呵呵，代码送给你

#include <stdio.h>
#define len 40000
int main（)
{
int m,n,i,j,mid,up,down,max;
int a[len],d[len];
while（scanf（"%d",&n)==1) //输入一共有几位同学
{
for（i=0;i <n;i++)
scanf（"%d",&a[i]); //用a数组记录这n位同学的身高
d[0]=-1;
d[1]=a[0];
max=1;
for（i=1;i <n;i++) //查找每个同学是否在最长子序列里
{
down=0;
up=max;
while（down <=up) //用d数组记录最x长子序列的最小身高是多少
{
mid=（up+down)/2;
if（d[mid] <a[i]) down=mid+1;
else up=mid-1;
}
d[down]=a[i];
if（down> max) max++; //这里采用二分法查找d数组，满足nlogn
}
printf（"%d\n",n-max); //打印最少出列的同学数
}
return 0;
}

发表于：2007-10-19 23:20:204楼得分:0

谢谢啦！！

发表于：2007-10-20 10:05:095楼得分:0

客气， acming....

其他资讯