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