19.接水问题

19.[NOIP2010 普及组] 接水问题
难度：普及/提高-
来源：NOIP普及组

![]

AC代码（C++/C#）：

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1010;
int n, m, p;
int s[N][N], cost[N];
int f[N], g[N][N];
struct Node
{
    int v, i, j;
    bool operator < (const Node & W) const
    {
        return v < W.v;
    }
};
priority_queue<Node> heap[N];
int get(int x)
{
    x %= n;
    if (x <= 0)
    {
        x += n;
    }
    return x;
}
int main(void)
{
    scanf("%d%d%d", &n, &m, &p);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            scanf("%d", &s[i][j]);
        }
    }
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (j == 1)
            {
                s[j][i] += s[n][i - 1];
            }
            else
            {
                s[j][i] += s[j - 1][i - 1];
            }
        }
    }
    memset(f, -0x3f, sizeof f);
    memset(g, -0x3f, sizeof g);
    f[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &cost[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        g[0][i] = -cost[get(i + 1)];
        heap[get(0 - i)].push({ g[0][i], 0, i });
    }
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            auto& h = heap[get(i - j)];
            while (h.size())
            {
                auto t = h.top();
                if (i - p > t.i)
                {
                    h.pop();
                }
                else
                {
                    f[i] = max(f[i], s[j][i] + t.v);
                    break;
                }
            }
        }
        for (int j = 1; j <= n; j++)
        {
            g[i][j] = f[i] - s[j][i] - cost[get(j + 1)];
            heap[get(i - j)].push({ g[i][j], i, j });
        }
    }
    int res = 0;
    for (int i = 0; i <= m; i++)
    {
        res = max(res, f[i]);
    }
    cout << res << endl;
    return 0;
}

没有注释，自行学习。
by：ጿ ኈ ቼ ዽ ጿ

---

你的点赞和关注就是我更新题解的最大动力！

---

-----------------------------点个赞吧 ↓ ！-----------------------------