一.题目链接:
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 2
8
**/
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;
}