以下是 AT_abc004_4 [ABC004D] マーブル 的 C++ 题解，包含详细注释。

解法一：枚举排列 + 贪心（简单理解版）

#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int R, G, B;
    cin >> R >> G >> B;
    
    vector<int> cnt = {R, G, B};
    vector<int> order = {0, 1, 2};
    int ans = INT_MAX;
    
    // 枚举6种排列顺序
    do {
        int pos = 0;
        int total = 0;
        
        for (int i = 0; i < 3; i++) {
            int len = cnt[order[i]];
            if (len > 0) {
                // 区间 [pos, pos+len-1]
                // 移动距离 = 各位置坐标之和（因为初始都在0）
                for (int j = 0; j < len; j++) {
                    total += pos + j;
                }
                pos += len;
            }
        }
        
        ans = min(ans, total);
        
    } while (next_permutation(order.begin(), order.end()));
    
    cout << ans << endl;
    
    return 0;
}

解法二：动态规划（官方正解）

这是正确的解法，考虑了每种颜色弹珠的初始位置不同。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <climits>
using namespace std;

const int INF = 1e9;
const int OFFSET = 100;  // 偏移量，使坐标非负
const int SIZE = 210;     // 数组大小

int dp[2][SIZE][SIZE];   // 滚动数组

int main() {
    int R, G, B;
    cin >> R >> G >> B;
    
    // 初始化DP数组
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < SIZE; j++) {
            for (int k = 0; k < SIZE; k++) {
                dp[i][j][k] = INF;
            }
        }
    }
    
    // 初始状态：还没放置任何弹珠
    dp[0][OFFSET][OFFSET] = 0;
    
    int total = R + G + B;
    
    for (int i = 0; i < total; i++) {
        int cur = i % 2;
        int nxt = 1 - cur;
        
        // 重置下一层
        for (int j = 0; j < SIZE; j++) {
            for (int k = 0; k < SIZE; k++) {
                dp[nxt][j][k] = INF;
            }
        }
        
        // 枚举红色和绿色已经放置的数量
        for (int r = 0; r < SIZE; r++) {
            for (int g = 0; g < SIZE; g++) {
                if (dp[cur][r][g] >= INF) continue;
                
                int b = i - (r - OFFSET) - (g - OFFSET) + OFFSET;
                if (b < 0 || b >= SIZE) continue;
                
                // 当前位置放置红色弹珠
                if (i < R) {
                    int nr = r + 1;
                    int cost = dp[cur][r][g] + abs((nr - 1) - OFFSET - 0);
                    dp[nxt][nr][g] = min(dp[nxt][nr][g], cost);
                }
                
                // 当前位置放置绿色弹珠
                if (i >= R && i < R + G) {
                    int ng = g + 1;
                    int cost = dp[cur][r][g] + abs((ng - 1) - OFFSET - 100);
                    dp[nxt][r][ng] = min(dp[nxt][r][ng], cost);
                }
                
                // 当前位置放置蓝色弹珠
                if (i >= R + G) {
                    int nb = b + 1;
                    int cost = dp[cur][r][g] + abs((nb - 1) - OFFSET - 200);
                    dp[nxt][r][g] = min(dp[nxt][r][g], cost);
                }
            }
        }
    }
    
    // 输出结果
    cout << dp[total % 2][OFFSET + R][OFFSET + G] << endl;
    
    return 0;
}

解法三：优化版 DP（更清晰）

#include <iostream>
#include <algorithm>
#include <cmath>
#include <climits>
using namespace std;

const int INF = 1e9;

int main() {
    int R, G, B;
    cin >> R >> G >> B;
    
    // dp[r][g]: 已经放置了 r 个红色和 g 个绿色时的最小代价
    // 蓝色数量 = 已放置总数 - r - g
    // 由于 R,G,B <= 100，数组大小开 210 足够
    int dp[210][210];
    
    for (int i = 0; i < 210; i++) {
        for (int j = 0; j < 210; j++) {
            dp[i][j] = INF;
        }
    }
    
    dp[0][0] = 0;
    
    for (int pos = 0; pos < R + G + B; pos++) {
        // 从后往前更新，避免重复使用
        for (int r = R; r >= 0; r--) {
            for (int g = G; g >= 0; g--) {
                int b = pos - r - g;
                if (b < 0 || b > B) continue;
                if (dp[r][g] == INF) continue;
                
                int current = dp[r][g];
                
                // 放置红色
                if (r < R) {
                    int cost = abs(pos - 0);  // 红色初始位置在 0
                    dp[r + 1][g] = min(dp[r + 1][g], current + cost);
                }
                
                // 放置绿色
                if (g < G) {
                    int cost = abs(pos - 100);  // 绿色初始位置在 100
                    dp[r][g + 1] = min(dp[r][g + 1], current + cost);
                }
                
                // 放置蓝色
                if (b < B) {
                    int cost = abs(pos - 200);  // 蓝色初始位置在 200
                    dp[r][g] = min(dp[r][g], current + cost);
                }
            }
        }
    }
    
    cout << dp[R][G] << endl;
    
    return 0;
}

解法四：最简洁易懂版（推荐）

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const int INF = 1e9;

int main() {
    int R, G, B;
    cin >> R >> G >> B;
    
    // dp[i][j]: 已经放置了 i 个红色和 j 个绿色时的最小代价
    int dp[105][105];
    
    for (int i = 0; i <= R; i++) {
        for (int j = 0; j <= G; j++) {
            dp[i][j] = INF;
        }
    }
    
    dp[0][0] = 0;
    
    // 枚举当前已经放置的总数
    for (int pos = 0; pos < R + G + B; pos++) {
        for (int r = R; r >= 0; r--) {
            for (int g = G; g >= 0; g--) {
                int b = pos - r - g;
                if (b < 0 || b > B) continue;
                if (dp[r][g] == INF) continue;
                
                int val = dp[r][g];
                
                // 尝试放红色
                if (r < R) {
                    dp[r + 1][g] = min(dp[r + 1][g], val + abs(pos - 0));
                }
                // 尝试放绿色
                if (g < G) {
                    dp[r][g + 1] = min(dp[r][g + 1], val + abs(pos - 100));
                }
                // 尝试放蓝色
                if (b < B) {
                    dp[r][g] = min(dp[r][g], val + abs(pos - 200));
                }
            }
        }
    }
    
    cout << dp[R][G] << endl;
    
    return 0;
}

样例验证

样例1

输入：2 1 1
输出：6

样例2

输入：0 2 3
输出：9

样例3（自测）

输入：1 1 1
输出：?

算法复杂度

• 时间复杂度：O(R × G × (R+G+B))，其中 R,G,B ≤ 100，最坏约 100³ = 1e6，完全可以接受
• 空间复杂度：O(R × G)，约 10000

核心思想

1. 三种颜色弹珠初始位置不同：

   • 红色：位置 0
   • 绿色：位置 100
   • 蓝色：位置 200

2. 我们需要将弹珠按顺序摆放在整数位置上（位置 0, 1, 2, ...）

3. 使用动态规划，依次决定每个位置放什么颜色的弹珠

4. dp[r][g] 表示已经放置了 r 个红色和 g 个绿色时的最小移动距离

5. 最终答案为 dp[R][G]