POJ2393
POJ2393
一週間ぶりくらいですね 今回は貪欲法の練習として解きました
ヒントに32bitより大きい整数になるかもしれないぞって書いてあるのにそれに気づかず悩んでました。
考え方としては、その週で買ったコストと保存しておくコストの和と、出荷する週で買ったコストのどちらが小さいかを選択していきました。 直感的な数学力のなさから最初は何個か保存しておいて足りない分を出荷する週で買う場合も存在するのかなって思ったので、微分して確かめたりしました。
あと、最初英語がよくわからなくて英語頑張らないとなあと思いました
解答時間は50分です。 以下コードです
#include <stdio.h> int n, s, store = 0; int y[10000], c[10000]; long long cost = 0; long long solve(){ for(int i = 0; i < n; i++){ cost += store * s; if(y[i] > store){ cost += (y[i] - store) * c[i]; store = 0; }else{ store -= y[i]; } for(int j = i+1; j < n; j++){ if(c[j] - c[i] - s * (j - i) > 0){ cost += y[j] * c[i]; store += y[j]; }else{ break; } } } return cost; } int main(){ scanf("%d %d", &n, &s); for(int i = 0; i < n; i++){ scanf("%d %d", &c[i], &y[i]); } printf("%lld\n", solve()); return 0; }