社区讨论
求助,总感觉这样做是错的
P1901发射站参与者 3已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @mi6yur2f
- 此快照首次捕获于
- 2025/11/20 13:03 4 个月前
- 此快照最后确认于
- 2025/11/20 13:03 4 个月前
貌似题解也基本是这样:
CPP维护一个单调栈(我的是递减),每遇到新的发射站,如果高于栈顶,就把栈顶的值加到新的发射站里然后退栈,一直重复到栈顶高于当前发射站,然后给栈顶加上当前发射站的值,当前发射站入栈。
但是蒟蒻的我总感觉如果这样做,每次往右传递了好多次能量,往左只传递一次能量啊QAQ,是我理解错了还是说这样能得出正解啊
CPPint n, h[maxn], v[maxn], sum[maxn], ans;
stack <int> s; //单调递减栈
int main(){
n = rd();
for(int i=1 ; i<=n ; i++){
h[i] = rd();
v[i] = rd();
while(s.size() && h[s.top()] < h[i]){ //向右加?
sum[i] += v[s.top()];
s.pop();
}
if(s.size()) sum[s.top()] += v[i]; //向左加?
s.push(i);
}
for(int i=1 ; i<=n ; i++)
ans = max(ans, sum[i]);
printf("%d\n", ans);
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...