计算最长双调序列……
这个算法还是可以继续优化的吧,应该是有O(NlnN)的算法,先考虑一下单调增序列的情况:扫描到元素时a[i],只要找到一个可以扩展的最长序列即可,因为可以证明如果a[i]包含在最优子序列里,那么一定也包含这个子序列,这是最优子结构就不用多说了。唯一tricky的一点就是注意到长度为k的序列的最小末尾元素一定是比长度为k+1的序列的最小末尾元素小的,这个可以用归纳法证明
对于折线序列,也是一样的,无非就是个最长的递减序列了,同样可以binary search呀binary search~但是懒了,不写了,写binary search最容易出错了~额~
#include <stdio.h>
#include <stdlib.h>
template<class T>
static inline void checkMax(T& dst, T src) {
if (src > dst) dst = src;
}
static int solve(int* h, int n)
{
int* longest_up;
int* longest_turn;
longest_up = (int*) malloc(sizeof(int) * n);
longest_turn = (int*) malloc(sizeof(int) * n);
longest_up[0] = 1;
for (int i = 1; i < n; i++) {
longest_up[i] = 1;
for (int j = 0; j < i; j++) {
if (h[i] > h[j])
checkMax(longest_up[i], longest_up[j] + 1);
}
}
longest_turn[0] = 1;
for (int i = 1; i < n; i++) {
longest_turn[i] = 1;
for (int j = 0; j < i; j++) {
if (h[i] < h[j]) {
checkMax(longest_turn[i], longest_turn[j] + 1);
checkMax(longest_turn[i], longest_up[j] + 1);
}
}
}
int max_len = 0;
for (int i = 0; i < n; i++) {
checkMax(max_len, longest_turn[i]);
checkMax(max_len, longest_up[i]);
}
free(longest_up);
free(longest_turn);
return n - max_len;
}
int main()
{
int n;
int h[300];
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &h[i]);
printf("%d\n", solve(h, n));
}
|
阅读(973) | 评论(0) | 转发(0) |