[PS規格-5.2]9465号:シール

問題情報

白駿9465号-ショートカット 難易度：シルバー2 アルゴリズムアルゴリズム:ダイナミックプログラミングダイナミックプログラミング

コメント

[Parameters] col:マップ列 status:0は左側に任意のマップxが含まれていることを示し、1は左上にマップが含まれていることを示し、2は左下にマップが含まれていることを示します [base case] マップ列の最後 [Logic] resultのデフォルト値はstatusが0で、statusが1でない場合は上部セルのマップが含まれ、次のステップを確認します。また、2でない場合は、下の欄のシールを含めて、次のステップを確認します。これらの値から最大値を選択し、注記再構築+リカバリを行います。

ソースコード

<タワータイプ>

#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <vector>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;

int score[2][100001];
int dp[100001][3];
int n;

int sticker(int col, int status) {

	if (col == n) return 0; // base case
	if (dp[col][status] != -1) return dp[col][status]; // memoization

	int result = sticker(col + 1, 0);
	if (status != 1) {
		result = max(result, score[0][col] + sticker(col + 1, 1));
	}
	if (status != 2) {
		result = max(result, score[1][col] + sticker(col + 1, 2));
	}
	dp[col][status] = result;
	return result;
}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> n;
		for (int a = 0; a < 2; a++) {
			for (int j = 0; j < n; j++) {
				int tp;
				cin >> tp;
				score[a][j] = tp;
			}
		}
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < 3; k++) {
				dp[j][k] = -1;
			}
		}
		cout << sticker(0, 0) << "\n";
	}
	
}

<起動方式>-by zzoni

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T; cin >> T;
    for (int t = 0; t < T; t++) {
        int N; cin >> N;
        int dp[2][100001]; // 최대값들의 합 배열
        int sc[2][100001]; // 점수 저장 배열
        for (int j = 0; j < 2; j++) {
            for (int k = 1; k <= N; k++)
                cin >> sc[j][k];
        }
        dp[0][0] = dp[1][0] = 0;
        dp[0][1] = sc[0][1]; dp[1][1] = sc[1][1];
        for (int i = 2; i <= N; i++) {
            dp[0][i] = max(dp[1][i - 1], dp[1][i - 2]) + sc[0][i];
            dp[1][i] = max(dp[0][i - 1], dp[0][i - 2]) + sc[1][i];
        }
        cout << max(dp[0][N], dp[1][N])<<"\n";
    }

    return 0;
}