社区讨论

求助,总感觉这样做是错的

P1901发射站参与者 3已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mi6yur2f
此快照首次捕获于
2025/11/20 13:03
4 个月前
此快照最后确认于
2025/11/20 13:03
4 个月前
查看原帖
貌似题解也基本是这样:
CPP
维护一个单调栈(我的是递减),每遇到新的发射站,如果高于栈顶,就把栈顶的值加到新的发射站里然后退栈,一直重复到栈顶高于当前发射站,然后给栈顶加上当前发射站的值,当前发射站入栈。
但是蒟蒻的我总感觉如果这样做,每次往右传递了好多次能量,往左只传递一次能量啊QAQ,是我理解错了还是说这样能得出正解啊
CPP
int 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 条回复,欢迎继续交流。

正在加载回复...