[白俊1943]硬貨配分
質問:1943銅貨配分
タイプ:DP
アイデア:金額の合計は10万を超えないので、半分に分けるために、5万以下の金額のうち、入力された合計の半分が生成できるかどうかを確認すればいいのです.
注記:dpテーブルはi円を作成できるかどうかを設定します.iメタの作成をループ入力できる場合は、0は保存されません.前のインデックスが次のインデックスに影響するため、タワーメソッドが使用されます.
コード#コード#
#include <bits/stdc++.h>
const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };
using namespace std;
int n, t = 3, dp[50001], sum;
pair<int, int> v[101];
int main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
while (t--) {
cin >> n;
sum = 0;
for (int i = 1; i <= n; i++) {
cin >> v[i].first >> v[i].second;
sum += v[i].first * v[i].second;
}
memset(dp, 0, sizeof(dp));
if (sum % 2 == 1) cout << 0 << '\n';
else {
dp[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 50000; j >= v[i].first; j--) {
if (dp[j - v[i].first]) {
for (int k = 0; k < v[i].second && j + k * v[i].first <= 50000; k++) {
dp[j + k * v[i].first] = 1;
}
}
}
}
cout << dp[sum / 2] << '\n';
}
}
return 0;
}Reference
この問題について([白俊1943]硬貨配分), 我々は、より多くの情報をここで見つけました https://velog.io/@asdsa2134/백준-1943-동전-분배テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol