题解 | 石子合并

#include <iostream>
#include <vector>

int main() {
    int n;
    std::cin >> n;
    std::vector<int> w(n);
    for (int i = 0; i < n; i++) {
        std::cin >> w[i];
    }
    int score = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            score += w[i] * w[j];
        }
    }
    std::cout << score << std::endl;
}
// 64 位输出请用 printf("%lld")

题目解析：

假设有四堆石子，分别是a、b、c、d。怎么样才最优解，我显示想到动态规划，但是试验了后发现不行。那排列顺序会有影响吗，那就先假设a <= b <= c <= d。先按从小到大的顺序合并：ab + (a + b)c + (a + b + c)d = ab + ac + bc + ad + bd + cd。再按从大到小顺序合并：dc + (d + c)b + (d + c + b)a，可以得出与从小到大顺序的结果一样。随机顺序也是一样的。而且可以发现结果是两两相乘之和。直接模拟就得出。