kojingharangの日記

SRM 568 Div1 250 BallsSeparating

08:01 |

• N個の箱があってR,G,B色のボールが箱iにそれぞれR[i],G[i],B[i]個入っている。すべての箱について１色のボールだけが含まれるようにするには、ボールをとってどこかに入れる作業を最低何回やる必要があるか返す問題。無理なら -1 を返す。
• 1≦N≦50, 1≦R[i],G[i],B[i]≦1000000

• 箱に対して色を決めると、その箱に関するコストが決まる。どこに入れるかはとりあえず考えない
• 最終的にR,G,Bの箱がそれぞれ1個以上あればよい
• 色の決め方は、概ねコスト最小の色を選んでいけばよさそうだが、そうすると全く使われない色がある場合になんかきな臭い。
• DPでやってみる
• dp[i][bit] ... i番目までの箱について１色しかないようにして、かつ使われた箱の色の組み合わせがbit==R<<2|G<<1|Bである場合の最小コスト
• １個前の箱までの色の組み合わせを prev, 今の箱までの色の組み合わせを cur, 今の箱を色 c にするとして
• (prev|1<<c)==cur になるなら前の箱までのコスト + 今回のコストで今の箱までのやつを更新する</li>
• 全部使うときの最小コストなので dp[N][7] がこたえ

• accepted ... だが遅い

#define INF 1<<30

class BallsSeparating {
	public:
	int minOperations(vector <int> R, vector <int> G, vector <int> B) {
		int N=R.size();
		VVI dp(N+1, VI(8, INF));
		dp[0][0]=0;
		
		RANGE(i, 1, N+1) {
			REP(cur, 8) {
				REP(prev, 8) {
					int costs[3];
					int all = R[i-1]+G[i-1]+B[i-1];
					costs[0] = all - R[i-1];
					costs[1] = all - G[i-1];
					costs[2] = all - B[i-1];
					REP(c, 3) {
						if((prev|(1<<c))==cur) {
							dp[i][cur] = min(dp[i][cur], dp[i-1][prev] + costs[c]);
						}
					}
				}
			}
			//cout<<i<<"::: "<<dp<<endl;
		}
		return dp[N][7]==INF ? -1 : dp[N][7];
	}
};

ツイートする