14202: 【原4202】植树节

题目

题目描述

author: flypig 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4202

植树节

题目描述

春天到了，同学们在阳光明媚的周六来到小花园，他们站成一圈，想在一个环形的草地上均匀地种上\(n\)棵树，但是每个位置的土壤都有它适合种的树的种类，种在合适的土壤上可以提升这种树的观赏价值。

同学们打算种\(3\)种树，这3种树的高度分别为\(10,20,30\)。同学们希望把这一圈树种得有层次感，所以任何一个位置的树都要求比它相邻的两棵树的高度都高或者都低，在这个条件下，同学们希望知道如何植树，才能使观赏价值总和最高。

输入格式

第一行一个整数\(n\)，表示需要种的树的棵树。

接下来\(n\)行，每行\(3\)个不超过\(10000\)的正整数\(a_i, b_i, c_i\)，分别表示了在第\(i\)个位置种高度为\(10,20,30\)的树能获得的观赏价值。

第\(i\)个位置的树与第\(i+1\)个位置的树相邻，特别地请注意，第\(1\)个位置的树与第\(n\)个位置的树相邻。

输出格式

一个正整数，为最大的观赏价值和。

样例输入

样例输出

数据规模

对于20%的数据有 \(n\leq10\) 对于40%的数据有 \(n\leq100\)
对于60%的数据有 \(n\leq1000\)
对于100%的数据有 \(4\leq n\leq100000\)，并保证n一定为偶数。

BugenZhao's solution

//
// Created by BugenZhao on 2019/3/18.
//
// 环拆链 动态规划
// 0 矮 1 两边高的中等 2 两边低的中等 3 高

#include <cstdio>
#include <algorithm>

using namespace std;

int value[100005][3];
int ans[100005][4];

int main() {
    int n;

    scanf("%d", &n);
    for (int k = 1; k <= n; ++k) {
        scanf("%d%d%d", &value[k][0], &value[k][1], &value[k][2]);
    }

    int maxAns = -0x7fffffff;

    for (int i = 0; i < 4; ++i) {
        ans[1][i] = -0x7fffffff;
    }
    ans[1][0] = value[1][0];
    for (int j = 2; j <= n; ++j) {
        ans[j][0] = max(ans[j - 1][2], ans[j - 1][3]) + value[j][0];
        ans[j][1] = ans[j - 1][3] + value[j][1];
        ans[j][2] = ans[j - 1][0] + value[j][1];
        ans[j][3] = max(ans[j - 1][0], ans[j - 1][1]) + value[j][2];
    }
    maxAns = max(maxAns, max(ans[n][2], ans[n][3]));

    for (int i = 0; i < 4; ++i) {
        ans[1][i] = -0x7fffffff;
    }
    ans[1][1] = value[1][1];
    for (int j = 2; j <= n; ++j) {
        ans[j][0] = max(ans[j - 1][2], ans[j - 1][3]) + value[j][0];
        ans[j][1] = ans[j - 1][3] + value[j][1];
        ans[j][2] = ans[j - 1][0] + value[j][1];
        ans[j][3] = max(ans[j - 1][0], ans[j - 1][1]) + value[j][2];
    }
    maxAns = max(maxAns, ans[n][3]);

    for (int i = 0; i < 4; ++i) {
        ans[1][i] = -0x7fffffff;
    }
    ans[1][2] = value[1][1];
    for (int j = 2; j <= n; ++j) {
        ans[j][0] = max(ans[j - 1][2], ans[j - 1][3]) + value[j][0];
        ans[j][1] = ans[j - 1][3] + value[j][1];
        ans[j][2] = ans[j - 1][0] + value[j][1];
        ans[j][3] = max(ans[j - 1][0], ans[j - 1][1]) + value[j][2];
    }
    maxAns = max(maxAns, ans[n][0]);

    for (int i = 0; i < 4; ++i) {
        ans[1][i] = -0x7fffffff;
    }
    ans[1][3] = value[1][2];
    for (int j = 2; j <= n; ++j) {
        ans[j][0] = max(ans[j - 1][2], ans[j - 1][3]) + value[j][0];
        ans[j][1] = ans[j - 1][3] + value[j][1];
        ans[j][2] = ans[j - 1][0] + value[j][1];
        ans[j][3] = max(ans[j - 1][0], ans[j - 1][1]) + value[j][2];
    }
    maxAns = max(maxAns, max(ans[n][0], ans[n][1]));

    printf("%d", maxAns);
    return 0;
}

skyzh's solution

#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>

using namespace std;

int dp[100000][3][3];
int _data[100000][3];
int N;

int print_dp() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                cout << j << " " << k << " " << dp[i][j][k] << endl;
            }
            cout << endl;
        }
        cout << endl;
    }
}

int dp_first(int k1) {
    memset(dp, 0, sizeof(dp));
    for (int j = 0; j < 3; j++) 
        for (int k = 0; k < 3; k++)
            if (k != k1) dp[0][j][k] = INT_MIN;
            else dp[0][j][k] = _data[0][k];
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < 3; j++) {
            for (int x2 = 0; x2 < 3; x2++) {
                int _m = INT_MIN;
                for (int x1 = 0; x1 < 3; x1++) {
                    if (x1 < x2 && x2 > j || x1 > x2 && x2 < j) {
                        _m = max(dp[i - 1][x1][x2] + _data[i][j], _m);
                    }
                }
                dp[i][x2][j] = _m;
            }
        }
    }
    int result = 0;
    for (int x1 = 0; x1 < 3; x1++) {
        if (k1 == 0) {
            for (int x2 = 1; x2 < 3; x2++) {
                result = max(result, dp[N - 1][x1][x2]);
            }
        }
        if (k1 == 2) {
            for (int x2 = 0; x2 < 2; x2++) {
                result = max(result, dp[N - 1][x1][x2]);
            }
        }
    }
    return result;
}

int dp_second(int k2) {
    memset(dp, 0, sizeof(dp));
    for (int j = 0; j < 3; j++) 
        for (int k = 0; k < 3; k++)
            if (k != k2 || j != 1) dp[1][j][k] = INT_MIN;
            else dp[1][j][k] = _data[1][k] + _data[0][j];
    for (int i = 2; i < N; i++) {
        for (int j = 0; j < 3; j++) {
            for (int x2 = 0; x2 < 3; x2++) {
                int _m = INT_MIN;
                for (int x1 = 0; x1 < 3; x1++) {
                    if (x1 < x2 && x2 > j || x1 > x2 && x2 < j) {
                        _m = max(dp[i - 1][x1][x2] + _data[i][j], _m);
                    }
                }
                dp[i][x2][j] = _m;
            }
        }
    }
    int result = 0;
    for (int x1 = 0; x1 < 3; x1++) {
        if (k2 == 0) {
            result = max(result, dp[N - 1][x1][0]);
        }
        if (k2 == 2) {
            result = max(result, dp[N - 1][x1][2]);
        }
    }
    return result;            
}

int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d%d%d", &_data[i][0], &_data[i][1], &_data[i][2]);
    }
    int dp0 = dp_first(0);
    int dp1 = dp_second(0);
    int dp2 = dp_second(2);
    int dp3 = dp_first(2);
    printf("%d\n", max(max(max(dp0, dp1), dp2), dp3));
    return 0;
}