蒟蒻在思考一道题推出思路时被下面这个问题卡住了,请问这题如何求解?(如果洛谷有原题或者类似的题话麻烦发一下链接,谢谢力)
今有长度为 n (1≤n≤105) n \ (1 \le n \le 10^{5})n (1≤n≤105) 的数组 aaa 和数组 bbb ,对于 ∀i∈[1,n]\forall i \in [1,n]∀i∈[1,n] ,有 ai,bi∈[1,103]a_{i},b_{i} \in [1,10^3]ai,bi∈[1,103] 。现有 ans=0ans = 0ans=0 ,我们要进行如下 nnn 次操作:
操作依次如下:
选定一个 iii ,要求 bi≠0 b_{i} \ne 0bi=0
令 bi=0b_{i} = 0bi=0
计算 ans=ans+ai∑i=1nbians = ans + a_{i} \sum_{i = 1}^{n}b_ians=ans+ai∑i=1nbi
求 ansansans 的最大值