AlgorithmStudy/17404.cpp at master · blackdurumi/AlgorithmStudy · GitHub

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
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <algorithm>
#include <climits>
#include <cstring>
#define N 1005

using namespace std;

int arr[N][3], D[N][3], ans = INT_MAX, ban;

int d(int n, int f)
{
    if (n == 1 && ban == f)
        return 99999999;
    if (D[n][f] != -1)
        return D[n][f];

    return D[n][f] = arr[n][f] + min(d(n - 1, (f + 1) % 3), d(n - 1, (f + 2) % 3));
}

int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int i, j, k, n;
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> arr[i][0] >> arr[i][1] >> arr[i][2];

    for (i = 0; i < 3; i++)
    {
        memset(D, -1, sizeof(D));
        D[1][0] = arr[1][0];
        D[1][1] = arr[1][1];
        D[1][2] = arr[1][2];

        ban = i;
        ans = min(ans, d(n, i));
    }

    cout << ans;

    return 0;
}