UVA 12002 Happy Birthday（dp+LIS）
浏览数：50 /
时间：2015年06月11日
链接：12002 - Happy Birthday
题意：一排的盘子，你一个个走过去，可以选择拿盘子，加在上面或下面，但是要保证上面的盘子一定小于等于下面的盘子，问最多拿几个。
思路：LIS的变形，先找出每个位置的LIS和LDS（注意相等也可以），然后枚举每个位置的LIS（LDS），加上往后找一个比他小（大）作为LDS（LIS）的开头，然后相加就是答案，维护最小值。
代码：
#include <stdio.h>
#include <string.h>
#define max(a,b) ((a)>(b)?(a):(b))
const int N = 505;
int n, k[N], i, j, lis[N], lds[N];
int main() {
while (~scanf("%d", &n) && n) {
int ans = 0;
for (i = 1; i <= n; i++)
scanf("%d", &k[i]);
for (i = n; i >= 1; i--) {
lis[i] = lds[i] = 1;
for (j = n; j > i; j--) {
if (k[i] <= k[j])
lis[i] = max(lis[i], lis[j] + 1);
if (k[i] >= k[j])
lds[i] = max(lds[i], lds[j] + 1);
}
}
for (i = 1; i <= n; i++) {
ans = max(ans, lis[i]);
ans = max(ans, lds[i]);
for (j = i + 1; j <= n; j++) {
if (k[j] < k[i])
ans = max(ans, lis[i] + lds[j]);
else if (k[j] > k[i])
ans = max(ans, lis[j] + lds[i]);
}
}
printf("%d\n", ans);
}
return 0;
}郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
