C语言高手请教:合唱队形算法

补充之后就懂了~~呵呵。这个程序TC下测试成功，好累，懒得写注释了，有时间了给你解释。先贴出来，你copy到TC里面可以直接用，没有人机交互，例如提示输入n之类的，你就按顺序先输入n在输入身高就好了，不过身高输入的时候一定要3位一空格，也就是就算只有50厘米也要输入050再空格。后来自己又考虑了一下，算法还是有缺陷，晚上我再想。困了。。。

#include<stdioh>

#include<stdlibh>

#include<stringh>

int main()

{

int n,test[100],len,k,flag;

char read=malloc(512sizeof(char));

do{

k=0;

for(len=0;len<100;len++)

test[len]=0;

flag=1;

scanf("%d\n",&n);

if(n<2||n>100)

exit(0);

if(n!=0)

fgets(read,512,stdin);

len=strlen(read)-1;

read[len]='\0';

for(len=0;len<n;len++){

test[len]=atoi(read);

read+=4;

}

for(len=0;len<n;len++){

if(test[len]<test[len+1]){

flag=0;

continue;

}

else{

if(flag)

k+=1;

else

break;

}

}

for(;len<n;len++){

if(test[len]>test[len+1])

continue;

else

k+=1;

}

printf("%d\n",k);

}while(n!=0);

return 0;

}

呵呵。我们先瞥开dp不看。解决这个问题我们这么考虑：

肯定有一个中间人，然后在他左边的人都要比他矮，并且是单调上升；在他右边的人肯定要比他矮，并且是单调下降！那么我们有了这个中间人，并且知道他的身高和他的位置，然后就是做左边的最长单调上升序列，加上右边的最长单调下降序列！

这个中间人，我们来枚举他，那么是不是只要解决最长单调上升序列和最长单调下降序列了？

这个单调上升序列和单调下降序列就用dp来求解！求解单调下降序列其实就是把一个数列反过来求最长单调上升序列吧？那么我就来讲一下单调上升序列。

给一个序列，求最长单调上升序列，我们用up[i]表示从第一个人到第i个人，最长的序列长。（就是到第i个人，必须身高单调上升，最多取多少人）

显然up[1]=1。

up[2]等于什么？如果2这个人比1高，那么up[2]=up[1]+1，要不就等于1是吧？

我们知道了up[1]和up[2]能不能知道up[3]呢？当然可以！因为如果3的人比2高，那么up〔3〕的值就可以取up[2]+1！

于是我们可以得出结论：

第i个人如果比第j个人高（i>j），那么up[i]就可以取up[j]+1！

那么就得出：

Up[i]=max{up[j]+1((0<j<i) and a[j]<a[i]),up[i-1]}

这里你还要注意一个问题，就是求出这个，但是a[i]必须小于中间人高度，这个up[i]才可取～

理解了么？

我们枚举一个中间人，ans=左边最长单调上升序列＋右边最长单调下降序列＋1(1就是中间这个人)

一个中间人对应一个ans，枚举中间人，求出最大的ans

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

我觉得说得很清楚了丫，up[i]表示到第i个人的最长上升子序列。

如果a[i]>a[j](i>j),那么up[i]的值就可以取up[j]+1（就是到第i个人的最长上升子序列加上第i个人）

于是我们对所有i，对j做一个循环。

得出Up[i]=max{up[j]+1((0<j<i) and a[j]<a[i]),up[i-1]}

以上就是关于C语言高手请教:合唱队形算法全部的内容，包括:C语言高手请教:合唱队形算法、Pascal编程题（合唱队形）、等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！