NC25834. 希望
描述
那一瞬间，一道白光闪过，从此大地上再也没有了丝毫的响动
那是一个黑暗的晚上。
新纪元59β年，23:13:56，这个悲惨的时刻。
所有人都开始自相残杀，亲人、朋友，都是敌人。
终有人类逃出了这片黑暗的天地，试图挽救这悲惨的未来。
但是腐化生物的能力完全超出了人类的控制范围。
勇者号的主控台与舰桥，人类最后与腐化生物抗衡的希望。
很可惜，α计划失败了，腐化生物即将入侵主控台。人类的最后英雄试图反抗。
这一切都是徒劳。
不！还有最后的希望！毁灭号的等离子充能炮！
如果不能得到，就将他彻底毁掉。
新纪元596α，下起了倾盆大雨，哭诉着勇者号自豪去死的英雄。
水宝宝驾驶着毁灭号接近了勇者号舰桥。
他要使用毁灭号的等离子炮摧毁勇者号主控台。
但是操控等离子炮的程序出了点问题。等离子炮有n个操作信号，第i个操作信号的强度为b[i]。总体强度为各操作信号的强度之和。
由于有些信号太弱了了 (强度<0)，水宝宝想把它们删除。但是水宝宝自己不会删除信号，所以他找来了同船的队友帮忙。
输入描述
输入格式：
第一行包含三个正整数 n,k,m
第二行包含 n个正整数 b1,b2,⋯,bn，表示各信号的强度。
接下来 m 行，每行三个正整数Li,Ri,Ci，表示一个队友的属性。
输出描述
输出格式：
输出一行一个整数，表示最大的信号强度
示例1
输入:
5 10 5 10 -2 -5 7 -10 1 1 5 2 4 10 4 4 12 3 4 10 1 5 15
输出:
5
说明:
样例解释：花费10的代价除掉a[3],答案即为10+7-10-2=5C++14(g++5.4) 解法, 执行用时: 204ms, 内存消耗: 14692K, 提交时间: 2020-03-17 12:42:10
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct node{
ll l,r,c;
bool operator<(const node& x) const{
if(c == x.c) return r<x.r;
return c < x.c;
}
};
ll n,k,m;
ll arr[100005];
multiset<node> s;
ll sum;
ll dp[555];
ll l,r,c;
vector<node> add[100005],del[100005];
int main(void){
sum = 0;
scanf("%lld %lld %lld",&n,&k,&m);
for(int i = 1;i<=n;++i){
scanf("%lld",&arr[i]);
sum += arr[i];
}
for(int i=1;i<=m;++i){
scanf("%lld %lld %lld",&l,&r,&c);
add[l].push_back({l,r,c});
del[r+1].push_back({l,r,c});
}
for(int i = 1;i<=n;++i){
for(node j:del[i]){
s.erase(j);
}
for(node j:add[i]){
s.insert(j);
}
if(arr[i] <= 0 && !s.empty()){
node tmp = *s.begin();
for(ll j = k;j>=tmp.c;--j){
dp[j] = max(dp[j],dp[j-tmp.c]-arr[i]);
}
}
}
printf("%lld\n",sum+dp[k]);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 212ms, 内存消耗: 3448K, 提交时间: 2020-01-12 14:49:21
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
#define ll long long
struct node{
int l,r,c;
}a[N];
ll sum,ans,b[N],c[N],dp[550];
int n,m,k,d[N];
bool cmp(node a,node b)
{
return a.c<b.c;
}
int main()
{
cin>>n>>k>>m;
for(int i=1;i<=n;i++)
cin>>b[i];
for(int i=1;i<=m;i++)
cin>>a[i].l>>a[i].r>>a[i].c;
sort(a+1,a+m+1,cmp);
int len=0;
memset(d,550,sizeof(d));
for(int i=1;i<=n;i++)
{
sum+=b[i];
if(b[i]<0)
{
c[++len]=-b[i];
for(int j=1;j<=m;j++)
{
if(i>=a[j].l&&i<=a[j].r)
{
d[len]=a[j].c;
break;
}}}}
for(int i=1;i<=len;i++)
for(int j=k;j>=d[i];j--)
dp[j]=max(dp[j],dp[j-d[i]]+c[i]);
cout<<sum+dp[k]<<endl;
return 0;
}