Too Young#
今日は模擬試験を受けて、20 点を取ることができました。
この問題セットは問題作成者が一貫して暴力的でしたが、今朝のジョークは良かったですね、——。
しかし、笑っているうちに笑えなくなりました。
そして、20 点を取ることができました。
多くの難問に囲まれた中で、簡単な問題セットを解くことは、心身を楽しませ、自信を高めることができます......
このように簡単な問題セットは、皆さんがすでに簡単に解けると思いますが、CSP-S ではそうはいかないかもしれません。CSP-S の最初の年も RP++ できることを願っています。楽しい競技です。
——問題作成者
私：？
これは最初の問題で、後の 2 つの問題はとてもNaNです。
問題#
大学の授業選択は本当に悩ましいことです！
マルコ：“私は 2 年で卒業したい！できるだけ多くの単位を取りたい！これらの授業は全部取りたい！”
長老："君はまだ若い！宿題の量を見て、全部やりきれるか？"
マルコ（笑顔が消えていく.gif）：“ではどうすればいいのですか？”
長老："どうすればいいと思う？授業をドロップしろ！"
マルコは $N (1 \leq N \leq 500)$ 個の授業を選択しました。それぞれの授業には単位数 $w_i$、労働度 $v_i$、落単率 $p_i$ があります。
ここで、$w_i$ は $[1,5]$ の範囲の正の整数、$v_i$ は int の範囲の正の整数、$p_i$ は $[0,1]$ の範囲の小数です。
マルコは自分の労働度をできるだけ小さくするために、いくつかの授業をドロップしたいと思っていますが、マルコの単位数が与えられた $MINX$ に達しない場合、彼は退学させられます。
マルコは、期待される単位数が $MINX$ 以上の場合、最小の労働度はいくつかを知りたいと思っています。
注意：もし授業に落単した場合、マルコは $v_i$ の労働度を支払いますが、対応する単位数を獲得することはできません。そうでなければ、マルコは $v_i$ の労働度を支払い、$w_i$ の単位数を獲得します。
入力形式#
最初の行には、授業の数を表す正の整数 $N$ があります。
次の $N$ 行には、スペースで区切られた $3$ つの数 $w_i,v_i$ および $p_i$ があります。これらは上記の説明に従います。
最後の行には、最小の単位数を表す正の整数 $MINX$ があります。
出力形式#
最小の労働度を表す正の整数を 1 行で出力してください。
データ範囲#
この問題には合計で 10 つのテストケースがあります。各テストケースは 10 ポイントです。
10% のテストケースについて、$1 \leq N \leq 10$
30% のテストケースについて、$1 \leq N \leq 20$
残りの 20% のテストケースについて、$p_i=0$
100% のテストケースについて、
$1 \leq N \leq 500$ ，
$w_i$ は正の整数であり、$1 \leq wi \leq 5$，
$p_i$ は小数点以下 2 桁まで含む小数であり、$0 \leq pi \leq 1$，
$v_i$ は int の範囲の正の整数です。
全ての授業を選択した場合、マルコは退学することはありません。
出力時に行末の余分なスペースは答えに影響しません。
入力例#
2
1 233 0
2 1 0.5
1
出力例#
1
解説#
2 番目の授業のみを選択し、期待される単位数は $2*0.5=1$ で、労働度は 1 です。
考え方#
最初に考えたのは、f[i][j] が第 i の授業まで考慮し、労働度が j のときに得られる最大のスコアを表すということでした。
しかし、j の範囲が広すぎます...
次に、f[i][j] を第 i の授業まで考慮し、期待されるスコアが j の最小の労働度を表すということを考えました。
しかし、期待されるスコアは小数です！！
その後、n<20 の場合は深さ優先探索、n>20 の場合は適当な DP を書いてみました。
この問題は全く解けませんでした。
解説を見てみると：
なるほど、なるほど！
あとは精度の問題があります。
唢呐さんの図を借りましょう。
なんですか？？
そして気づいたのですが、
100 - p * 100 ではだめなんですね
0.01 を加えるか、round(100 - p * 100) を使えばいいんですね？？
まあいいや、次からは round を使うことを覚えておきます。
コード#
たったこれだけです。。。
#include <cstdio>
#include <algorithm>
#include <cmath>
const int MAXN = 505;
int w[MAXN], v[MAXN];
long long f[MAXN * MAXN];
int n;
int minx;
int maxW = 0;
long long ans = (1ll<<60ll);
int main (void) {
freopen("young.in", "r", stdin);
freopen("young.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
double p;
scanf("%d%d", w + i, v + i);
scanf("%lf", &p);
w[i] *= round(100 - p * 100);
maxW += w[i];
}
scanf("%d", &minx);
minx *= 100;
for (int i = 1; i <= maxW; ++i) {
f[i] = (1ll<<60ll);
}
int sum = 0;
for (int i = 1; i <= n; ++i) {
sum += w[i];
for (int j = sum; j >= w[i]; --j) {
f[j] = std::min(f[j], f[j - w[i]] + v[i]);
}
}
for (int i = minx; i <= sum; ++i) {
ans = std::min(ans, f[i]);
}
printf("%lld\n", ans);
return 0;
}