TopCoder SRM 726 Div1 Easy Unpacking

この日CFでダメージを受けたので、SRM出ておいた方がよかったのかも。
https://community.topcoder.com/stat?c=problem_statement&pm=14759

問題

N個の箱があり、i番の箱には赤い飴がA[i]個、青い飴がB[i]個入っていることになっている。
ただし、購入時点で総数は変わらないが赤・青が１個増減する場合がある。

各箱の購入コストが与えられる。
赤と青の飴をいずれか片方確実にK個手に入れたい。
その場合の購入総コストの最小値を求めよ。

解法

以下のいずれかを満たすよう考えて、それぞれナップサック問題をDPで解けばよい。
飴が増減しても総数は変わらないので、確実に赤青いずれかK個を達成するために３つ目の戦略を取るところがポイント。

• 購入した箱にすべて(A[i]-1)個赤い飴が入っているとき、合計K個を超える最小コスト
• 購入した箱にすべて(B[i]-1)個青い飴が入っているとき、合計K個を超える最小コスト
• 飴の総購入数が(2K-1)個以上となる最小コスト

int dp[3][20101];

class Unpacking {
	public:
	int getcost(vector <int> a, vector <int> b, vector <int> cost, int K) {
		int N=a.size();
		int i,j;
		for(i=1;i<=20100;i++) dp[0][i]=dp[1][i]=dp[2][i]=1<<30;
		
		dp[0][0]=dp[1][0]=dp[2][0]=0;
		FOR(i,N) {
			for(j=20000;j>=0;j--) {
				dp[0][min(10000,j+max(0,a[i]-1))]=min(dp[0][min(10000,j+max(0,a[i]-1))],dp[0][j]+cost[i]);
				dp[1][min(10000,j+max(0,b[i]-1))]=min(dp[1][min(10000,j+max(0,b[i]-1))],dp[1][j]+cost[i]);
				dp[2][min(20000,j+a[i]+b[i])]=min(dp[2][min(20000,j+a[i]+b[i])],dp[2][j]+cost[i]);
			}
		}
		
		int mi=1<<30;
		for(i=K;i<=10000;i++) mi=min({mi,dp[0][i],dp[1][i]});
		for(i=2*K-1;i<=20000;i++) mi=min(mi,dp[2][i]);
		if(mi==1<<30) mi=-1;
		return mi;
	}
}

まとめ

これは割とすんなり思いついた。