UVA 12002 Happy Birthday(dp+LIS)

链接: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;
}


UVA 12002 Happy Birthday(dp+LIS),布布扣,bubuko.com

UVA 12002 Happy Birthday(dp+LIS)

上一篇:Android学习笔记02


下一篇:关于android出现不能下载相关依赖包,解决办法