問題へのリンク
考察
制約が小さめ。
↓
3次元のDP使えそう…
解くためのヒント
“うぅ~~自分で解けないよぉ~~~😰…”という方、
一度ヒントを書くので、このヒントを読んでもう一度だけ自分で解けるか挑戦してみてください。
まず、上で書いたようにこの問題は3次元のDPで解けます。
DP[i][j][k]:=i個目の弁当までで、たこ焼きをj個、たい焼きをk個買うために必要な弁当の数の最小値です。
では、DPの処理の一部だけ書いてみましょう。
以下のコードのコメント部分に遷移部分を書いてみてください
#include <bits/stdc++.h>
using namespace std;
const int MAX_COUNT = 300;
const int INF = 1e9;
template<typename T>
bool chmin(T &a, const T &b) {
if (a > b) {
a = b;
return true;
}
return false;
}
int main() {
int n, x, y;
cin >> n >> x >> y;
vector<pair<int, int> > lunch(n);
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
lunch[i] = {a, b};
}
//dp[i][j][k]:= i個目までの弁当で、たこ焼きをj個、たい焼きをk個買うために必要な"弁当の数の最小値"
//ただし、MAX_COUNTを超えた場合は、MAX_COUNTに丸めて考える
vector<vector<vector<int> > > dp(n + 1, vector<vector<int> >(MAX_COUNT + 1, vector<int>(MAX_COUNT + 1, INF)));
dp[0][0][0] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= MAX_COUNT; j++) {
for (int k = 0; k <= MAX_COUNT; k++) {
/////////////////////////////////////////////////////
//チャレンジ!! ここにDPの遷移部分を書いてみよう!!
//注意点としてこの実装では、MAX_COUNT(300)より大きい個数は、300としてみなす必要がある...
/////////////////////////////////////////////////////
}
}
}
//n個目の弁当まで見たときに、たこ焼きx個以上、たい焼きy個以上を食べている時の弁当の個数の最小値を探す
int min_lunch_count = INF;
for (int i = x; i <= MAX_COUNT; i++) {
for (int j = y; j <= MAX_COUNT; j++) {
chmin(min_lunch_count, dp[n][i][j]);
}
}
cout << (min_lunch_count == INF ? -1 : min_lunch_count);
}解けたでしょうか???…
(このヒントが役に立ったのなら良いのですが…)
ヒントを見ても解けなかった、WAだった方、答え合わせにいってみましょう🫠
下のACしたコードに上のコードの完成版があります。
ACしたコード
#include <bits/stdc++.h>
using namespace std;
const int MAX_COUNT = 300;
const int INF = 1e9;
template<typename T>
bool chmin(T &a, const T &b) {
if (a > b) {
a = b;
return true;
}
return false;
}
int main() {
int n, x, y;
cin >> n >> x >> y;
vector<pair<int, int> > lunch(n);
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
lunch[i] = {a, b};
}
//dp[i][j][k]:= i個目までの弁当で、たこ焼きをj個、たい焼きをk個買うために必要な"弁当の数の最小値"
//ただし、MAX_COUNTを超えた場合は、MAX_COUNTに丸めて考える
vector<vector<vector<int> > > dp(n + 1, vector<vector<int> >(MAX_COUNT + 1, vector<int>(MAX_COUNT + 1, INF)));
dp[0][0][0] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= MAX_COUNT; j++) {
for (int k = 0; k <= MAX_COUNT; k++) {
if (dp[i][j][k] == INF) continue;
//i番目の弁当を買わない場合
chmin(dp[i + 1][j][k], dp[i][j][k]);
//i番目の弁当を買う場合
const auto [takoyaki, taiyaki] = lunch[i];
//食べたい個数は最大でも300個なので、それを超えた場合は300に丸める
int next_j = min(j + takoyaki, MAX_COUNT);
int next_k = min(k + taiyaki, MAX_COUNT);
chmin(dp[i + 1][next_j][next_k], dp[i][j][k] + 1);
}
}
}
//n個目の弁当まで見たときに、たこ焼きx個以上、たい焼きy個以上を食べている時の弁当の個数の最小値を探す
int min_lunch_count = INF;
for (int i = x; i <= MAX_COUNT; i++) {
for (int j = y; j <= MAX_COUNT; j++) {
chmin(min_lunch_count, dp[n][i][j]);
}
}
cout << (min_lunch_count == INF ? -1 : min_lunch_count);
}さいごに
この問題のDiffは1085となっていて、私のような緑・またはそれ以下コーダーにとっては解けると美味しいです。
DPは遷移部分が見えさえすれば書きやすいので頑張って慣れていきましょう！！😍😍
以上、”EDPC-F LCSを1年8ヶ月放置している私”が書いたDP解法でしたっ!!
コメント