Codeforces 447D DZY Loves Modification

题意

给你一个n * m的矩阵，让你做K次操作，使得最后得到的值最大。

操作有两种：

一是在任意一行上操作，最终的结果值加上这一行数的和，然后这一行每一个数都要减去p。

二是在任意一列上操作，最终的结果值加上这一列数的和，然后这一列每一个数都要减去p。

数据范围：1 ≤ n, m ≤ 10^3; 1 ≤ k ≤ 10^6; 1 ≤ p ≤ 100

退化版的题目思路

如果我们只限定一种操作，此题就是简单题了。我们维护一个大根堆，堆中保存每一行（或列）之和。

每次操作只需要取出最大值，加到最终结果上。之后将这个值减去对应的p * n（或p * m），再加入堆中。

经过K次循环，就可以得到最后的答案了。

真正的题目思路

对于行和列同时操作，我们也可以套用这种方法。但是要解决对行操作后，对列上数字的值的影响。

易得，如果行列混合操作，且只使用上述方法的话。每次行操作所得到的值，实际上为简单行操作得到的值 - 此次行操作之前的所有列操作次数 * p(为什么？)。对于列操作亦然。

假设我们有一个操作序列，<a0, b0>代表序列的一段执行了a0个行操作和b0个列操作。如下图所示：

<a0, b0>  | <1, 0>  | <0, 1>  | <a1, b1>|
|<---A--->|<---B--->|<---C--->|<---D--->|

操作被分为了四个阶段。

对于B阶段来说，其结果为1次简单行操作的值 - b0 * p(为什么？)，对于C阶段来说，其结果为1次简单列操作的值 - (a0 + 1) * p。

那么，如果当我们把B阶段和C阶段互换的话，结果是不变的。(为什么？我真TMD是十万个为什么。。。)

所以我们可以得出，在任一个操作序列中，我们可以交换任意一个的行操作和列操作，而总结果不变。

最终，我们可以将操作序列等价变化成下面的序列。

<a, 0> | <0, b>

此时，最终的结果为a次简单行操作的值 + b次简单列操作的值 - a * b * p。(为什么？)

而a与b的值可以简单的通过枚举得到。思路有了，代码如果不出大问题，这题就可以AC了。

代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

#define print(x) cout << x << endl
#define input(x) cin >> x

typedef long long llint;

const int SIZE = 1024;
const int K = 1024000;

int n, m, k, p;
llint sumX[K + 5], sumY[K + 5];
vector<llint> xs, ys;

void do_calc(const vector<llint>& vs, llint sum[], int u)
{
    priority_queue<llint> pq;
    for (auto i: vs) {
        pq.push(i);
    }
    sum[0] = 0;
    for (int i = 1; i <= k; i++) {
        llint now = pq.top();
        pq.pop();
        sum[i] = sum[i - 1] + now;
        now -= (llint)p * u;
        pq.push(now);
    }
}

void calcX()
{
    do_calc(xs, sumX, m);
}

void calcY()
{
    do_calc(ys, sumY, n);
}

int main()
{
    int a;
    freopen("input.txt", "r", stdin);
    input(n >> m >> k >> p);
    ys.resize(m);
    xs.resize(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &a);
            ys[j] += a;
            xs[i] += a;
        }
    }

    calcX();
    calcY();

    llint ans = std::numeric_limits<llint>::min();
    for (int i = 0; i <= k; i++) {
        llint t = 0;
        t += sumX[i];
        t += sumY[k - i];
        t -= (llint)i * (k - i) * p;
        ans = max(ans, t);
    }
    print(ans);
    return 0;
}

后记

某厂的g++版本是3.4.x，没有C++11，根本秀不起来啊！

说的就和你会写C++11一样_(:з」∠)_

题意

退化版的题目思路

真正的题目思路

代码

后记

Comments