|
|
题目大意：
给出一个序列，序列里的数字都是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;
}
|