题解 | #QQ10 石子合并#(模拟)

解题思路

1.可证明任意合并顺序所获得分均一样,简单模拟即可;

代码

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

int main(){
    int n;
    cin >> n;
    vector<int> w(n);
    for(int i = 0; i < n; i++){
        cin >> w[i];
    }
    int score = 0, sum = w[0];
    for(int i = 1; i < n; i++){ //任意合并顺序得分均一样
        score += sum * w[i]; //sum表示前一个石堆的石子个数
        sum += w[i];
    }
    cout << score;
    return 0;
}