TopCoder SRM 765 : Div1 Hard SteelMill

適当にやっても解に到達してしまいそう。
https://community.topcoder.com/stat?c=problem_statement&pm=15696&rd=17678

問題

N個の鉱山からGキログラムの金属を生成したい。　
各鉱山を利用する場合、固定コストとして運搬コストC[i]がかかり、そこでとれた鉱石から金属を生成すると1キロ当たりP[i]のコストがかかる。
また、鉱山から取れる金属はS[i]キロである。

計Gキログラムの金属を生成する最小コストを求めよ。

解法

仮に使う鉱山が決まっている場合、できるだけ単価の安い鉱山から使うのがよく、Gキログラム以上取れるなら単価の高い材料を避けるのが良い。
そこで、鉱山をP昇順にソートし、以下をDPで求める。
f(i,k) := 先頭i個までの鉱山で計kキログラム作るときの最小コスト
とし、
f(i,min(goal,k+S[i])) := f(i-1,k)+C[i]+P[i]*(min(goal,k+S[i])-k)
で表を埋めていくとよい。

Editorialは表を埋める方向が異なるので、Pを降順にソートしているね。

class SteelMill {
	public:
	long long cheapest(int goal, vector <int> shipmentCost, vector <int> shipmentSize, vector <int> costPerKg) {
		vector<pair<int,int>> P;
		int N=shipmentCost.size();
		int i;
		FOR(i,N) P.push_back({costPerKg[i],i});
		sort(ALL(P));
		//reverse(ALL(P));
		
		vector<ll> dp(goal+1,1LL<<61);
		dp[0]=0;
		FORR(p,P) {
			int i=p.second,j;
			for(j=goal;j>=0;j--) {
				int tar=min(goal,j+shipmentSize[i]);
				dp[tar]=min(dp[tar],dp[j]+shipmentCost[i]+1LL*costPerKg[i]*(tar-j));
			}
		}
		return dp[goal];
		
	}
}

まとめ

Mediumさっさと切り上げてこっちやればよかったか。