|
|
題目大意：
給出一個序列，序列里的數字都是1~3，比如：
1 3 2 1 1
你可以改變任意一個數字。
問：最少改變多少次，能使序列變成升序序列或者降序序列。
比如第一個1改成3，使它變成 3 3 2 1 1，就變成降序序列了。
思路：
從后往前推，先考慮變成升序序列的情況。
定義：
f[3][i] = 最后一個元素到第i個元素全部改變為3所需要的次數
f[2][i] = 最后一個元素到第i個元素改變為22222...33333...所需要的最小次數
f[1][i] = 最后一個元素到第i個元素改變為11111...22222...33333所需要的最小次數
那么 f[1][1] 就是答案了。
可見，對于第i個元素：
f[3]很容易計算出來
f[2] = min{ f[3][i-1], (第i個元素 == 2) + f[2][i-1] }
f[1] = min{ f[2][i-1], (第i個元素 == 1) + f[1][i-1] }
那么復雜度就是 O(N) 了。降序序列一樣處理，從前往后推。
優化：
輸入序列里面的一長串一樣的元素可以一段一段處理
f數組可以變成滾動數組
代碼：
這個算法應該還算可以的，看到Disscuss里面有人說用“最長不降子序列”來做，還不知道用那個怎么做。。
最長不降子序列，好像求出長度的貪心算法是 O(NlgN)，求出序列的動規算法是 O(N^2)。
但是好像那些人提交的代碼都挺快的，0ms
我的代碼比較爛，32ms。。想不通啊。。
 #include <stdio.h>
#include <string.h>
  struct  {
 int val, len;
 } in[30024];
int in_cnt;
int num_cnt[4], f[4][2];
__inline int min(int a, int b)
{
return a < b ? a : b;
}
int main()
{
int i, n, val, a, b;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d", &n);
  for (i = 0; i < n; i++) {
scanf("%d", &val);
if (val != in[in_cnt].val)
in[++in_cnt].val = val;
in[in_cnt].len++;
 }
for (i = in_cnt; i >= 1; i--) {
num_cnt[in[i].val] += in[i].len;
f[3][i&1] = num_cnt[2] + num_cnt[1];
f[2][i&1] = min(f[3][i&1], (in[i].val!=2)*in[i].len + f[2][(i-1)&1]);
f[1][i&1] = min(f[2][i&1], (in[i].val!=1)*in[i].len + f[1][(i-1)&1]);
}
a = f[1][(i-1)&1];
memset(num_cnt, 0, sizeof(num_cnt));
memset(f, 0, sizeof(f));
for (i = 1; i <= in_cnt; i++) {
num_cnt[in[i].val] += in[i].len;
f[3][i&1] = num_cnt[2] + num_cnt[1];
f[2][i&1] = min(f[3][i&1], (in[i].val!=2)*in[i].len + f[2][(i-1)&1]);
f[1][i&1] = min(f[2][i&1], (in[i].val!=1)*in[i].len + f[1][(i-1)&1]);
}
b = f[1][(i-1)&1];
printf("%d\n", min(a, b));
return 0;
}
|