P6471 [COCI2008-2009#6] DOSTAVA 题解

_Spectator_ · 2024-10-06 10:29:29 · 题解

可能更好的食用体验 | 题目传送门 | 我的其他题解

{\color{#00CD00}\text{题意}}

给定一张 n\times m 的网格，每个格子 (i,j) 上有一个权值 a_{i,j}。可以在网格上任意左右移动，但只有在第 1 列或者第 m 列才能上下移动。现在要从 (1,1) 出发依次经过 D 个不同的格子，求经过的格子的权值之和的最小值。

{\color{#00CD00}\text{思路}}

将每一个点都作为状态进行考虑显然不现实。注意到“只有在第 1 列或者第 m 列才能上下移动”，不难想到将每一行的第 1 个点和第 m 个点作为状态进行考虑。这样就将原图拆分为了 2\times n 个状态，其中第 i 行第 1 的点的编号为 i，第 i 行第 m 的点的编号为 i+n。

接下来可以在这些状态之间连边。连边方式也比较显然：
对于第 i 行，

从 i 向 i+n 连一条边，权值为 \sum a_i - a_{i,m}。
从 i+n 向 i 连一条边，权值为 \sum a_i - a_{i,1}。
若 i>1，从 i 向 i-1 连权值为 a_{i,1} 的边，同时从 i+n 向 i\!-\!1\!+\!n 连权值为 a_{i,m} 的边。
若 i<n，从 i 向 i+1 连权值为 a_{i,1} 的边，同时从 i+n 向 i\!+\!1\!+\!n 连权值为 a_{i,m} 的边。

其中 \sum a_i 表示第 i 行所有 a_{i,j} 的和。减去 a_{i,m} 和 a_{i,1} 是为了避免算重。

这样我们就建出了一张图。定义 f_{i,j} 表示由状态 i 到状态 j 的最小花费时间。可以用多源最短路算法求解。

使用 \bf floyd 算法，时间复杂度为 O(n^3)，可以通过 70\% 的数据。
使用 \bf Dijkstra 算法，以每一个点为原点跑一遍 \rm dijkstra，时间复杂度为 O(n^2\log n)，可以通过本题。

求得 f 数组后，对于每一个询问 (tx,ty)\to (x,y)，分类讨论出最短时间即可。注意不要忘了讨论 tx=x 的情况，即起点与终点在同一行。

代码实现上需要注意：

long long。
数组要开 2 倍大。
可以预处理出前缀和、后缀和来优化实现。
留意 corner case，避免转角处的点的权值被重复计算或漏算。

本题实现较繁琐，具体细节可参见代码。

{\color{#00CD00}\text{代码}}

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i=a; i<=b; i++)
#define req(i, a, b) for(int i=a; i>=b; i--)
#define add(u, v, w) G[u].push_back({v, w})
using namespace std;
const int N = 2e3 + 5, M = 2e2 + 5, inf = 2e9 + 5;
typedef pair<int, int> pii;
long long n, m, Q, ans; //其实只有这个 ans 需要开 long long
int a[N][M], s[N][M], r[N][M];
int vis[N<<1], f[N<<1][N<<1];
vector<pii> G[N<<1];
void dijkstra(int s, int *dis){ //dijkstra 算法 
    priority_queue<pii, vector<pii>, greater<pii>> q;
    fill(dis, dis+1+n*2, inf), fill(vis, vis+1+n*2, 0);
    dis[s] = 0, q.push({0, s});
    while(!q.empty()){
        int d = q.top().first, u = q.top().second; q.pop();
        if(vis[u]) continue; vis[u] = 1;
        for(pii i:G[u]){
            int v = i.first, w = i.second;
            if(d + w < dis[v]) dis[v] = d + w, q.push({dis[v], v});
        }
    }
}
signed main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> n >> m;
    rep(i, 1, n) rep(j, 1, m) cin >> a[i][j]; //读入 
    rep(i, 1, n) rep(j, 1, m) s[i][j] = s[i][j-1] + a[i][j]; //前缀和 
    rep(i, 1, n) req(j, m, 1) r[i][j] = r[i][j+1] + a[i][j]; //后缀和
    rep(i, 1, n){ //建图
        if(i > 1) add(i, i-1, a[i][1]), add(i+n, i-1+n, a[i][m]);
        if(i < n) add(i, i+1, a[i][1]), add(i+n, i+1+n, a[i][m]);
        add(i, i+n, s[i][m] - a[i][m]), add(i+n, i, s[i][m] - a[i][1]);
    }
    rep(i, 1, n*2) dijkstra(i, f[i]); //多源最短路 
    int tx=1, ty=1;
    for(cin >> Q; Q --> 0;){ //分类讨论处理询问 
        int x, y; cin >> x >> y;
        int res0 = tx ^ x ? inf : y < ty ? s[x][ty] - s[x][y] : s[x][y-1] - s[x][ty-1];
        int res1 = s[tx][ty] - a[tx][1] + f[tx][x] + s[x][y] - a[x][y];
        int res2 = r[tx][ty] - a[tx][m] + f[tx+n][x] + s[x][y] - a[x][y];
        int res3 = s[tx][ty] - a[tx][1] + f[tx][x+n] + r[x][y] - a[x][y];
        int res4 = r[tx][ty] - a[tx][m] + f[tx+n][x+n] + r[x][y] - a[x][y];
        ans += min({res0, res1, res2, res3, res4}); tx = x, ty = y;
    }
    cout << ans + a[tx][ty];
    return 0;
}

AC Record

附：本题有一道加强版，那题的时限只有 200ms，需要使用 dp 解决。