【NOIPシミュレーション】小奇掘鉱
2846 ワード
前に书いた逆プッシュspfa今日はDP逆プッシュ~一中私达の建设の下でやっと自分のOjプル~やはり私の脚本の効率が高い~自动伝題~OJアドレス伝说の中の小奇は1匹のニャー~テーマの背景です
小奇はいくつかの鉱物を採掘し、ドリル(初期能力値w)を持つ宇宙船を運転し、既定のルートでニャンコ系のnつの星を順次飛んだ.
【問題の説明】
星は2種類に分けられる:資源型と修理型.1.資源型:鉱物質量a[i]を含む、採掘を選択するとa[i]pの金銭が得られ、その後ドリル損失k%、すなわちp=p(1-0.01 k)2.メンテナンスタイプ:メンテナンス費用b[i]、メンテナンスを選択した場合、b[i]pのお金を支払い、その後ドリル修復c%、すなわちp=p(1+0.01 c)(pはドリル現在の能力値)注:メンテナンス後ドリルの能力値は初期値を超えることができますこの収入を最大化することを決定してください
【入力形式】
最初の行の4つの整数n,k,c,w.以下のn行、各行2個の整数type,x.typeが1であることは資源型星を表し、xはそのミネラル含有量a[i]である.typeが2の場合はメンテナンス型星を表し、xはメンテナンス費用b[i]である.
【出力形式】
1行1実数(小数2桁保持)を出力し、要求された結果を表します.
【サンプル入力】
5 50 50 10 1 10 1 20 2 10 2 20 1 30
【サンプル出力】
375.00
【データ範囲】
30%のデータに対してn<=100は50%のデータに対してn<=1000,k=100は100%のデータに対してn<=100,000,0<=k,c,w,a[i],b[i]<=100は10^9を超えないことを保証する
小奇はいくつかの鉱物を採掘し、ドリル(初期能力値w)を持つ宇宙船を運転し、既定のルートでニャンコ系のnつの星を順次飛んだ.
【問題の説明】
星は2種類に分けられる:資源型と修理型.1.資源型:鉱物質量a[i]を含む、採掘を選択するとa[i]pの金銭が得られ、その後ドリル損失k%、すなわちp=p(1-0.01 k)2.メンテナンスタイプ:メンテナンス費用b[i]、メンテナンスを選択した場合、b[i]pのお金を支払い、その後ドリル修復c%、すなわちp=p(1+0.01 c)(pはドリル現在の能力値)注:メンテナンス後ドリルの能力値は初期値を超えることができますこの収入を最大化することを決定してください
【入力形式】
最初の行の4つの整数n,k,c,w.以下のn行、各行2個の整数type,x.typeが1であることは資源型星を表し、xはそのミネラル含有量a[i]である.typeが2の場合はメンテナンス型星を表し、xはメンテナンス費用b[i]である.
【出力形式】
1行1実数(小数2桁保持)を出力し、要求された結果を表します.
【サンプル入力】
5 50 50 10 1 10 1 20 2 10 2 20 1 30
【サンプル出力】
375.00
【データ範囲】
30%のデータに対してn<=100は50%のデータに対してn<=1000,k=100は100%のデータに対してn<=100,000,0<=k,c,w,a[i],b[i]<=100は10^9を超えないことを保証する
#include
#include
#include
#include
#include
#include
using namespace std;
int n;double k,c,w,ans;
struct ek{
int k;double c;
}e[110000];
int main(){
scanf("%d%lf%lf%lf",&n,&k,&c,&w);
for(int i=1;i<=n;i++)scanf("%d%lf",&e[i].k,&e[i].c);
ans=0.0;
for(int i=n;i>=1;i--){
if(e[i].k==1){
ans=max(ans,(ans*(1-k/100.0)+e[i].c*w));
}
else{
ans=max(ans,(ans*(1+c/100.0)-e[i].c*w));
}
}
printf("%.2lf
",ans);
return 0;
}