【模拟赛】【DP】2021.8.11.A

本文主要是介绍【模拟赛】【DP】2021.8.11.A，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

有n个数，可以进行m次操作，有k格能量，对于第i次操作，有$L_i,R_i,C_i$表示你可以将n个数中编号从$L_i$到$R_i$中任意数删去，但每删一个数就会消耗$C_i$格能量，求最终所有数的和最大为多少

思路

背包能过👍

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;ll A[100250], W[100250], L[100250], F[100250], B[100250];
ll n, m, k, sum, l, r, t, tot;int main()
{memset(B, 0x7f, sizeof(B));scanf("%lld%lld%lld", &n, &m, &tot);for(ll i = 1; i <= n; ++i)scanf("%lld", &A[i]), sum += A[i];for(ll i = 1; i <= m; ++i){scanf("%lld%lld%lld", &l, &r, &k);if(k > tot)continue;for(ll j = l; j <= r; ++j)B[j] = min(B[j], k);}for(ll i = 1; i <= n; ++i)if(A[i] < 0 && B[i] != B[0])W[++t] = B[i], L[t] = -A[i];for(ll i = 1; i <= t; ++i)for(ll j = tot; j >= W[i]; --j)F[j] = max(F[j], F[j - W[i]] + L[i]);printf("%lld", sum + F[tot]);return 0;
}

这篇关于【模拟赛】【DP】2021.8.11.A的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---