Upgrading Technology（2019牛客暑期多校训练营（第六场）J，预处理 + 枚举）

本文主要是介绍Upgrading Technology（2019牛客暑期多校训练营（第六场）J，预处理 + 枚举），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一.题目链接：

Upgrading Technology

二.题目大意：

有 n 件物品，每个物品都有 m 个等级.

当物品 i 从等级 j - 1 升级到时 j 时，需花费 c[i][j].

当所有物品都超过 j 级时，将会获得 d[j].

三.分析：

枚举最低等级，根据贪心的原则，第 i 件物品应取大于等于 j 等级的最大收益.

但由于最低等级为 j，所以应该减去最低的收益.

ps：不要忘记最低等级为 0 的情况.

四.代码实现：

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <bitset>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-8
#define lc k * 2
#define rc k * 2 + 1
#define pi acos(-1.0)
#define ll long long int
using namespace std;const int M = (int)1e3;
const ll mod = (ll)1e9 + 7;
const ll inf = 0x3f3f3f3f3f3f3f3f;ll ans, d, x, add;
ll sum[M + 5][M + 5], sum_max[M + 5][M + 5];/**
1
4 3
-1  -2  -0
-3  0  0
1  -1  1
3  -4  -1
-1 -1 28
**/int main()
{int T;scanf("%d", &T);for(int ca = 1; ca <= T; ++ca){int n, m;scanf("%d %d", &n, &m);for(int i = 1; i <= n; ++i){for(int j = 1; j <= m; ++j){scanf("%lld", &x);sum[i][j] = sum[i][j - 1] - x;}sum_max[i][m + 1] = -inf;for(int j = m; j >= 0; --j)sum_max[i][j] = max(sum_max[i][j + 1], sum[i][j]);}ans = d = 0;for(int i = 0; i <= m; ++i){add = inf;for(int j = 1; j <= n; ++j)add = min(add, sum_max[j][i] - sum[j][i]);add = -add;for(int j = 1; j <= n; ++j)add += sum_max[j][i];if(i){scanf("%lld", &x);d += x;}ans = max(ans, add + d);}printf("Case #%d: %lld\n", ca, ans);}return 0;
}

 

这篇关于Upgrading Technology（2019牛客暑期多校训练营（第六场）J，预处理 + 枚举）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---