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最后那个循环,已及,为什么合并是从前往后却是最优解。