Q&A
この問題ですが、以下のソースコードで何が間違っているのかわかりません。
方針としては、
1．一旦kのことを考えずにDP配列に重要度を格納
2．その際それに必要なスクショの数をsum_k配列に格納しておく
3．最後にsum_k配列でk以下のもので最大のものを出力
としています。
サンプルケースはすべて解答があっており、重要度・枚数の配列の中身が想定通りである
ことを確認したため詰まっております。
分かる方がいましたらら教えていただきたいです。
※ ほかのやり方についてはすでに調べているので、ほかの解法について紹介する
のではなく、このコードのどこが間違っているのかを教えていただきたいです。
宜しくお願い致します。
cpp
1#include <bits/stdc++.h> 2#define rep(i,n) for(int i=0;i<(n);++i) 3using namespace std; 4using ll=long long; 5int main(){ 6 int w,n,k;cin>>w>>n>>k; 7 vector<int> a(n),b(n); 8 rep(i,n)cin>>a[i]>>b[i]; 9 // スクショの重要度を格納するDP配列、枚数を格納するDP配列 10 ll dp[51][10010],sum_k[51][10010]; 11 rep(i,51)rep(j,10010)dp[i][j]=0,sum_k[i][j]=0; 12 13 rep(i,n)rep(sum_w,w+1){ 14 if(sum_w-a[i]>=0){ 15 dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w-a[i]]+b[i]); 16 17 // スクショを追加できる、且つ追加した方が重要度が大きくなる場合は1枚追加 18 // 追加しても重要度が変わらない場合は追加しない 19 if(dp[i][sum_w-a[i]]+b[i]>dp[i][sum_w])sum_k[i+1][sum_w]=sum_k[i][sum_w-a[i]]+1; 20 else sum_k[i+1][sum_w]=sum_k[i][sum_w]; 21 }else{ 22 // もしスクショを追加できない場合は、1列上の枚数のまま 23 sum_k[i+1][sum_w]=sum_k[i][sum_w]; 24 } 25 dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w]); 26 } 27 28 // 幅w以下、枚数k枚以下でもっとも重要度が高い値をcとして出力 29 long long c=0; 30 rep(sum_w,w+1){ 31 if(sum_k[n][sum_w]>k)continue; 32 c=max(c,dp[n][sum_w]); 33 } 34 cout<<c; 35}
回答1件
0
ベストアンサー
現状のやり方の問題点はK枚以下で作ることができる重要度の高い組み合わせを、K枚を超えて作る組み合わせで隠してしまってるところです。
text
13 23 1 31 2 41 2 52 3
こんなケースを考えてみて下さい。1枚目と2枚目のスクリーンショットを使うことで幅2重要度4の組み合わせになりますが、結局これはK枚を超える組み合わせなので使えません。
一方で3枚目のスクリーンショットだけを使って幅2重要度3の組み合わせができますが、それは前記の組み合わせより重要度が低いので無視されます。
この問題にはパラメーターが重要度と枚数と幅の3つあって、重要度はできるだけ大きく、枚数と幅はできるだけ小さくする組み合わせを求めるというのがざっくりとした内容です。
今のコードのように幅を添え字にして重要度と枚数を記録するようにした場合、重要度は大きいが枚数も多いような組み合わせと重要度は小さいが枚数も少ないような組み合わせのどちらを記録すべきかということは一概には言えません。
3つのうち2つを添え字にして残り一つを記録する方法とはここが大きく違って難易度は相当上がってるはずです。(私は思いつきません)
投稿2020/05/23 15:42
編集2020/05/24 10:02
総合スコア2047
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2020/05/24 00:48
2020/05/24 13:48