Topcoder Single Round Match 568
Problem Statement
There are N boxes numbered from 0 to N-1, inclusive. For each i, box i contains red[i] red balls, green[i] green balls, and blue[i] blue balls.
Fox Ciel wants to separate the balls by colors. In each operation, she can pick a single ball from some box and put it into another box. She considers the balls to be separated if no box contains balls of more than one color.
Return the minimal number of operations required to separate the balls. If this is impossible, return -1.
Definition
Class: BallsSeparating
Method: minOperations
Parameters: int[], int[], int[]
Returns: int
Method signature: int minOperations(int[] red, int[] green, int[] blue)
(be sure your method is public)
Constraints
- red, green and blue will each contain between 1 and 50 elements, inclusive.
- red, green and blue will contain the same number of elements.
- Each element of red, green and blue will be between 1 and 1,000,000, inclusive.
'
Java代码
public class BallsSeparating {
public static void main(String[] args) {
BallsSeparating bs = new BallsSeparating();
int[] red = {842398, 491273, 958925, 849859, 771363, 67803, 184892, 391907, 256150, 75799};
int[] green = {268944, 342402, 894352, 228640, 903885, 908656, 414271, 292588, 852057, 889141};
int[] blue = {662939, 340220, 600081, 390298, 376707, 372199, 435097, 40266, 145590, 505103};
int ans = bs.minOperations(red, green, blue);
System.out.println(ans);
}
public int minOperations(int[] red, int[] green, int[] blue) {
int boxNum = red.length;
if (boxNum < 3) {
return -1;
}
int dp[][] = new int[8][boxNum + 1];
for (int i = 0; i < 8; i++) {
for (int j = 0; j <= boxNum; j++) {
dp[i][j] = -1;
}
}
dp[0][0] = 0;
for (int i = 1; i <= boxNum; i++) {
int r = red[i - 1];
int g = green[i - 1];
int b = blue[i - 1];
for (int k = 0; k < 3; k++) {
for (int j = 0; j < 8; j++) {
//BGR
int code = getCode(j,k);
int val = getValue(r,g,b,k);
if (dp[j][i - 1] >= 0) {
if (dp[code][i] < 0)
dp[code][i] = dp[j][i - 1] + val;
else
dp[code][i] = Math.min(dp[code][i], dp[j][i - 1] + val);
}
System.out.print(dp[code][i] + " ");
}
System.out.println();
}
System.out.println();
}
return dp[7][boxNum];
}
public int getValue(int r, int g, int b, int color) {
if (color == 0) //B
return r + g;
else if (color == 1) //G
return r + b;
else //R
return g + b;
}
//210
//RGB
public int getCode(int curCode, int color) {
return curCode | (1 << color);
}
}
本文链接：https://bookshadow.com/weblog/2014/05/10/topcoder-srm-568-balls-separating/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
如果这篇博客对你有帮助，请支持书影博客
你的捐赠将用于服务器与域名费用，帮助免费技术内容持续更新。
支付宝
微信
建议金额：¥5 / ¥10 / ¥20 / ¥50（扫码后自行输入）