若すぎる#
今日は模擬試験を一セットやって、20 点を達成しました。
この問題は出題者が全程暴力的で %、今朝のジョークが良かった、——。
しかし、笑っているうちに笑えなくなりました。
そして 20 点を達成しました。
多くの厄介な問題に囲まれている中で、簡単な水問題が一つ、心身を楽しませ、信頼を高めることができます......
こんなに簡単な問題は皆さんも楽に AK できたと思いますが、CSP-S はそう簡単ではないかもしれません。皆さんが CSP-S の初年度も RP++ できて、楽しく競技できることを願っています。
——出題者
私：？
これは第一問で、後の二問はあまりにもNaNです。
問題#
大学の選択科目は本当に悩ましいことですね！
Marco：“私は 2 年で卒業したい！できるだけ多くの単位を取りたい！これらの授業はすべて選択する！”
長者："君は、若すぎる！宿題の量を見て、終わらせられるのか？"
Marco（笑顔が徐々に消える.gif）：” それじゃあどうすればいいの？“
長者：" どうするって？退学すればいいじゃない！“
Marco は $N (1 \leq N \leq 500)$ の科目を選択し、それぞれの科目には単位 $w_i$ 、労力 $v_i$ と不合格確率 $p_i$ がある；
ここで、$w_i$ は $[1,5]$ の範囲内の正の整数、$v_i$ は int 範囲内の正の整数、$p_i$ は $[0,1]$ の範囲内の小数です；
現在、Marco は自分の労力をできるだけ小さくするためにいくつかの科目を退学したいと思っていますが、もし Marco の単位の合計が指定された $MINX$ に達しない場合、彼は退学されます。
Marco は、期待単位が $MINX$ 以上である場合、彼の最小労力はどれくらいか知りたいと思っています。
注意：もし一つの科目で不合格になった場合、Marco は $v_i$ の労力を支払いますが、相応の単位を得ることはできません；そうでなければ、Marco は $v_i$ の労力を支払い、$w_i$ の単位を得ます。
入力形式#
第一行に正の整数 $N$ が科目の数を示します。
次の $N$ 行には、空白で区切られた $3$ つの数 $w_i,v_i$ と $p_i$ があり、意味は問題文の通りです。
最後の行に正の整数 $MINX$ が必要な最小学分を示します。
出力形式#
一行に最小労力を示す正の整数を出力します。
データ範囲#
この問題には 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 w_i \leq 5$，
$p_i$ は最大 2 桁の小数を含み、$0 \leq p_i \leq 1$，
$v_i$ は int 範囲内の正の整数です。
全選択の状況下で Marco が退学されないことを保証します。
出力時に各行の末尾の余分な空白は、答えの正確性に影響しません。
サンプル入力#
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,dfsを適当に書いて、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;
}