Algoogle

Algorithm for Programming Contest

PKU 3670 Eating Together

Category: PKU Tag: dp

Eating Together

問題概要


解法


123の順と321の順の両方試す.
各牛について
dp[i][j] := i の番号を j にするときの変更の最小回数
123の順でやるときは i 番目のカードの番号を j にするには
j 以下の番号から遷移できる.
321の順でやるときは i 番目のカードの番号を j にするには
j 以上の番号から遷移できる.

コード


(3670.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <algorithm>
#include <cstdio>

using namespace std;

int N;
int num[30010];
int dp[30010][3];

int main(){
    scanf("%d", &N);
    for(int i = 0; i < N; i++){
        scanf("%d", num+i);
        num[i]--;
    }

    for(int i = 0; i < N; i++)
        for(int j = 0; j < 3; j++){
            dp[i+1][j] = int(1e9);
            for(int k = 0; k <= j; k++)
                dp[i+1][j] = min(dp[i+1][j], dp[i][k] + int(j!=num[i]));
        }

    int ans = min(dp[N][0],min(dp[N][1],dp[N][2]));

    for(int i = 0; i < 3; i++) dp[0][i] = 0;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < 3; j++){
            dp[i+1][j] = int(1e9);
            for(int k = j; k < 3; k++)
                dp[i+1][j] = min(dp[i+1][j], dp[i][k] + int(j!=num[i]));
        }
    ans = min(ans, min(dp[N][0],min(dp[N][1],dp[N][2])));
    printf("%d\n", ans);
    return 0;
}

Comments