温州微信网站定制,乐东黎族自治县住房建设局网站,网站美工设计什么是平衡,跨境电商开店奶牛的歌声
jzoj 1256
题目大意
有n头牛#xff0c;每头牛的声音可以被两边第一头比他高的牛所听到#xff0c;音量为S#xff0c;问听到声音的音量之和最大的牛听到的音量之和是多少
输入样例
3
4 2
3 5
6 10输出样例
7样例解释
队伍中有3头奶牛#xff0c;第1头牛…奶牛的歌声
jzoj 1256
题目大意
有n头牛每头牛的声音可以被两边第一头比他高的牛所听到音量为S问听到声音的音量之和最大的牛听到的音量之和是多少
输入样例
3
4 2
3 5
6 10输出样例
7样例解释
队伍中有3头奶牛第1头牛的身高是4音量是2其余依此类推。 队伍中的第3头奶牛可以听到第1头和第2头奶牛的歌声于是她能听到的总音量为257。虽然她唱歌时的音量为10但并没有奶牛可以听见她的歌声。
解题思路
用一个单调下降的栈来存每头牛的声音没遇到一头牛就把比他小的一部分加进这头牛然后他入队 以此类推 时间复杂度o(n)o(n)o(n)
代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
using namespace std;
ll n, dep, anss, h[50500], s[50500], z[50500], ans[50500];
int main()
{scanf(%lld, n);for (ll i 1; i n; i){scanf(%lld%lld, h[i], s[i]);while(dep h[i] h[z[dep]])ans[i] s[z[dep--]];//当前牛能听见的z[dep] i;//他的声音}dep 0;for (ll i n; i 0; --i)//另一个方向{while(dep h[i] h[z[dep]])ans[i] s[z[dep--]];z[dep] i;}for (ll i 1; i n; i)anss max(anss, ans[i]);printf(%lld, anss);return 0;
}
