回答編集履歴
1
詳細説明
test
CHANGED
|
@@ -1,3 +1,15 @@
|
|
|
1
|
-
dp[i][j][k]は、**i枚目までの中から、幅がjでかつk枚張り付けた場合の重要度の最大値**を意味することになります。そうなると、最後に出力しているdp[N][W][K]は、**幅がWでK枚張り付けた場合の重要度の最大値**となります。ところが、入力例の説明にもある通り、**必ずしもK枚使う必要がなく、また幅も必ずしもWと一致する必要がない**
|
|
1
|
+
dp[i][j][k]は、**i枚目までの中から、幅がjでかつk枚張り付けた場合の重要度の最大値**を意味することになります。そうなると、最後に出力しているdp[N][W][K]は、**幅がWでK枚張り付けた場合の重要度の最大値**となります。ところが、入力例の説明にもある通り、**必ずしもK枚使う必要がなく、また幅も必ずしもWと一致する必要がない**と考えられます。
|
|
2
|
+
|
|
3
|
+
例えばK=10,W=30のような状況で、
|
|
4
|
+
|
|
5
|
+
- 5枚で幅28、重要度200になる組み合わせがあるが、幅2のスクリーンショットが存在せず幅30にできない
|
|
6
|
+
|
|
7
|
+
- 6枚で幅30になる組み合わせは存在するものの、その重要度の合計が180となり、最大にならない
|
|
8
|
+
|
|
9
|
+
|
|
10
|
+
|
|
11
|
+
という状況が考えられます。これでもこのプログラムは「10枚で幅30の重要度」を表示しますが、この例でそれは実現不可能のため、0を出力する結果となります。当然不正解となります。
|
|
12
|
+
|
|
13
|
+
このプログラムで正解となるのは、K枚で幅Wを埋めて、かつ条件内での重要度が最大になる、というかなりのレアケースになります。
|
|
2
14
|
|
|
3
15
|
そのため、動的計画法を使いながら、重要度の最大値を記録しておく必要があると思います。
|