NOIP2004--合唱队形 合唱队形noip

再写DP,是一道经典中的经典。

中文题,不解释了。可参考RQNOJ-26 和TYVJ-1067。

题解:分别设f[i]和g[i]表示为:

第i个以前的最长上升序列数和第i个以后的最长下降序列数。

然后枚举k,答案就是Min (n-(f[k]+g[k]-1))

也就是,第k个点的左右之和的最大值减去重复的自己,取用最大值是因为存活人数最多,踢掉人数最少。

不罗嗦了,看代码,我喜欢的就是Max函数,我只用一个,利用函数的tmp参数来表示。

代码:

#include<stdio.h>
#include <stdlib.h>
#include<string.h>

intheight[105], n;

int Max(int array[105], int left, int right, int tmp) {
int i, max =0, k = tmp == 1 ? right : left;
for (i =left; i <= right; i++) {
if (height[i] >= height[k] || array[i] == 0)
continue;
max = max < array[i] ? array[i] : max;
}
returnmax;
}

int dp(int now) {
intf[now+1], g[now+1], i, max = 0;
memset (f,0, sizeof (f));
memset (g,0, sizeof (g));
f[1] =1;
for (i = 2;i <= now; i++)
f[i] = Max (f, 1, i, 1) + 1;
g[n] =1;
for (i =n-1; i >= 1; i--)
g[i] = Max (g, i, n, -1) + 1;
for (i = 1;i <= n; i++)
if (max < f[i]+g[i]-1)
max = f[i]+g[i]-1;
returnmax;
NOIP2004--合唱队形 合唱队形noip
}

int main () {
int i;
scanf ("%d",&n);
for (i = 1;i <= n; i++)
scanf ("%d", &height[i]);
printf("%d", n - dp (n));
//system("pause");
return0;
}
For NOIP, Fighting !

  

爱华网本文地址 » http://www.413yy.cn/a/25101010/26588.html

更多阅读

《让生命精彩》高一级校歌合唱比赛简报 复旦大学校歌合唱

由著名诗人、词作家蒋开儒作词,著名曲作家李昕作曲的校歌《让生命精彩》高度概括了我校“和谐发展,卓越创新”的先进办学理念,浓缩了侨中大气、厚重的校园文化,显示了侨中人执著的向往与追求。为了弘扬校园文化,让高一新生领悟校歌意蕴,感

声明:《NOIP2004--合唱队形 合唱队形noip》为网友叫自己放手分享!如侵犯到您的合法权益请联系我们删除