可持久化动态图上树状数组维护01背包

本文主要是介绍可持久化动态图上树状数组维护01背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

来源：牛客网 —牛客练习赛29-A

题目链接：https://www.nowcoder.com/acm/contest/211/A

解题思路：如果该序列中有负数，从下标大依次向下标小的删数（从右向左），这样可以保证代价最小，此时为ans += i*m。负  数全部删完后，从下标小依次向下标大的删数（从左向右），此时正数所乘的下标最小，都为1，ans += m;

代码实现：

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int n, m, i;
ll ans;
int main()
{cin >> n;for(i=1; i<=n; i++){cin >> m;if(m < 0)ans += (ll)m*i;elseans += m;}cout << ans << endl;return 0;
}

 

这篇关于可持久化动态图上树状数组维护01背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---