POJ 3670 Eating Together

解法

状態が(場所, 最後に使ったカード)のdp

ソースコード

int min_ascending(const int* c, int n)
{
    const int inf = ten(8);
    int dp[3 * ten(4) + 100][3]; // (pos, last card)
    erep(i, n) rep(j, 3)
	dp[i][j] = inf;

    dp[0][0] = 0;
    rep(i, n) rep(j, 3)
    {
	for (int k = j; k < 3; ++k)
	    chmin(dp[i + 1][k], dp[i][j] + (c[i] != k));
    }

    int res = inf;
    rep(j, 3)
	chmin(res, dp[n][j]);
    return res;
}
int main()
{
    int n, c[3 * ten(4)];
    scanf("%d", &n);
    rep(i, n)
	scanf("%d", c + i), --c[i];

    int res = min_ascending(c, n);
    rep(i, n)
    {
	static const int table[] = { 2, 1, 0 };
	c[i] = table[c[i]];
    }
    chmin(res, min_ascending(c, n));
    printf("%d\n", res);
}