【深基5.习4】[USACO08OCT] Bovine Bones G

解题思路

三重循环枚举三个骰子的所有面，统计每种点数和的出现次数。由小到大扫描和，只在频次严格更高时替换答案。

正确性说明

每个组合等概率，出现次数最大即概率最大；升序扫描且不替换同频值保证取最小点数和。

易错点

骰子面从 1 开始；输出和，不是出现次数。

复杂度

时间 O(s1s2s3)，空间 O(s1+s2+s3)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a, b, c;
    cin >> a >> b >> c;
    vector<int> cnt(a + b + c + 1);
    for (int i = 1; i <= a; i++)
        for (int j = 1; j <= b; j++)
            for (int k = 1; k <= c; k++)
                cnt[i + j + k]++;
    int ans = 3;
    for (int s = 4; s <= a + b + c; s++)
        if (cnt[s] > cnt[ans])
            ans = s;
    cout << ans << "\n";
    return 0;
}