アルゴリズム::白準::DP:9465::シール
23984 ワード
質問する
質問リンク
尚根の妹は文房具屋で2 n枚のシールを買った.シールは図(a)に示すように2行n列に並べられている.やさしい人はシールで机を飾ります.
やさしく購入したシールの質が悪い.シールを1枚引き裂くと、それらのシールと共有エッジのシールが引き裂かれ、使用できません.つまり、外したシールの左、右、上、下のシールは使用できません.
すべてのシールが貼れない優しさは各シールに点数をつけ、点数の和が最大に達し、シールを引き裂きたいと思っています.まず、図(b)のように各シールに点数をつけます.やさしいシール点数の最値を求めるプログラムを作成してください.すなわち,2 n個のマップのうち,スコアの和が最大であり,互いに共有しないエッジのセットを求める必要がある.
上図では、点数50、50、100、60のシールを選択した場合、点数は260となり、これが最大点数となります.点数が一番高い2枚のシール(100と70)はエッジを共有しているので、同時に分けることはできません.
質問へのアクセス
コード#コード#
#include <iostream>
#include <cstring>
using namespace std;
int T, N, a[2][100000], dp[100000][3];
int solve(int n, int m) {
if (n < 0) return 0;
if (dp[n][m] >= 0) return dp[n][m];
if (m == 0) return dp[n][0] = max(solve(n - 1, 1), solve(n - 1, 2));
if (m == 1) return dp[n][1] = max(solve(n - 1, 0), solve(n - 1, 2)) + a[0][n];
return dp[n][2] = max(solve(n - 1, 0), solve(n - 1, 1)) + a[1][n];
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> T;
while (T--) {
memset(dp, -1, sizeof(dp));
memset(a, -1, sizeof(a));
cin >> N;
for (int i = 0; i < 2; ++i)
for (int j = 0; j < N; ++j) cin >> a[i][j];
dp[0][0] = 0, dp[0][1] = a[0][0], dp[0][2] = a[1][0];
cout << max(max(solve(N, 0), solve(N, 1)), solve(N, 2)) << '\n';
}
}あるいは、forwadingで解く
#include <iostream>
#include <cstring>
using namespace std;
int T, n, a[2][100001], dp[100001][3];
int solve() {
for (int i = 1; i <= n; ++i) {
dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]);
dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + a[0][i];
dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + a[1][i];
}
return max(max(dp[n][0], dp[n][1]), dp[n][2]);
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> T;
while(T--) {
cin >> n;
memset(a, 0, sizeof(a));
memset(dp, 0, sizeof(dp));
for(int i = 0; i < 2; ++i)
for (int j = 1; j <= n; ++j) cin >> a[i][j];
cout << solve() << '\n';
}
}結果
Reference
この問題について(アルゴリズム::白準::DP:9465::シール), 我々は、より多くの情報をここで見つけました https://velog.io/@embeddedjune/알고리즘-백준-DP-9465-스티커テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol