谁能帮我解释一下这个代码喵?

灌水区

lucy2012 @ 2024-08-10 17:34:32

七夕单身双身快乐喵~

好像解决的是石子合并,可是怎么用贪心?

#include<bits/stdc++.h>
using namespace std;
const int N = 50005;
int n, stone[N], ans, t = 1;

void solve(int k){
    int tmp = stone[k] + stone[k - 1];
    ans += tmp;
    for(int i = k; i < t - 1; i++)
        stone[i] = stone[i + 1];
    t--; int j = 0;
    for(j = k - 1; j > 0 && stone[j - 1] < tmp; j--)
        stone[j] = stone[j - 1];
    stone[j] = tmp;
    while(j >= 2 && stone[j] >= stone[j - 2]){
        int d = t - j; solve(j - 1);
        j = t - d;
    }
}

int main(){
    int n; cin >> n;
    for(int i = 0; i < n; i++)
        cin >> stone[i];
    for(int i = 1; i < n; i++){
        stone[t++] = stone[i];
        while(t >= 3 && stone[t - 3] <= stone[t - 1])
            solve(t - 2);
    }
    while(t > 1) solve(t - 1);
    cout << ans << endl;
    return 0;
}

by lucy2012 @ 2024-08-10 19:25:39

@SwethessPotion 那这个代码哪里模拟了队列喵?


by SwethessPotion @ 2024-08-10 19:32:00

大概就是这个 stone 数组了。。


by lucy2012 @ 2024-08-10 19:40:08

@SwethessPotion 呜,就是怎么模拟的?我还是有些看不懂。。比如solve最后那个循环,已及,为什么合并是从前往后却是最优解。


上一页 |