POJ 3670 Eating Together

POJ_3670

??? 由于遞增和遞減是類似的，下面不妨只討論變成遞增序列的情況。

??? 由于Di只有三個數，所以可以考慮將序列分割成三部分，第一部分全部變成1，第二部分全部變成2，第三部分全部變成3。然后我們枚舉3開始的位置，這時一共有若干決策，要么前面的全部是1，要么前面有一段2，然后再前面有一段1或者沒有，如果每種決策都考察一遍的話整體復雜度就要O(N^2)了，因此考慮優化一下。記當前的位置為i，1的最后一個位置為j，not1[k]表示k以及k之前不是1的數量，not2[k]表示k以及k之前不是2的數量，not3[k]表示k以及k之后不是3的數量，那么我們把決策表示成not2[i]+(not1[j]-not2[j])+not3[i+1]，這樣如果我們保留著前面所有j中not1[j]-not2[j]的最小值的話，就可以O(1)找到最優決策了。

??? 這個題目還有一個很好的思路就是直接求最長不降子序列，然后用N減去這個值，不過這樣最好也只是O(NlogN)的復雜度。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXD 30010
#define INF 0x3f3f3f3f
int N, not3[MAXD], a[MAXD];
void init()
{int i;for(i = 1; i <= N; i ++) scanf("%d", &a[i]);
}
int deal()
{int i, not1, not2, ans, opt;not3[N + 1] = 0;for(i = N; i >= 1; i --) not3[i] = not3[i + 1] + (a[i] != 3);ans = not3[1], not1 = not2 = opt = 0;for(i = 1; i <= N; i ++){if(a[i] != 1) ++ not1;if(a[i] != 2) ++ not2;opt = std::min(opt, not1 - not2);ans = std::min(ans, not2 + opt + not3[i + 1]);}return ans;
}
void solve()
{int i, ans = deal();for(i = 1; i <= N / 2; i ++) std::swap(a[i], a[N - i + 1]);ans = std::min(ans, deal());printf("%d\n", ans);
}
int main()
{while(scanf("%d", &N) == 1){init();solve();}return 0;
}

?

?

?