T4 - Constructive 题解

题目简述

题目大意：
给定 $N$ 种二维向量 $v_i = (a_i, b_i)$ 及其代价 $c_i$，每种向量可无限次使用。求构造出目标向量 $u = (x, y)$ 的最小总代价。

• 向量数量 $N \le 90$
• 目标坐标 $x, y \le 10^9$
• 向量分量 $a_i, b_i \le 10$
• 向量代价 $c_i \le 10^9$

子任务简析

从简单情况到一般情况的思考过程：

• Subtask 1: 步长为 1 的坐标移动，结果显而易见。
• Subtask 2 & 3: 坐标范围小，直接建图跑 Dijkstra。
• Subtask 4: 降维打击，转化为一维无界背包。
• Subtask 5: 大坐标直线路径，引入同余类 BFS/DP 思想。

正解

解法 1：分治（官方题解）

几何中点引理：
如果一组短向量的和为 $(x, y)$，那么我们通过调整顺序，一定可以把他们分成两半，使得每一半的和都在 $(\frac{x}{2}, \frac{y}{2})$ 的常数范围内。

转移方程：

$f(x, y) = \min_{\delta_x, \delta_y} \{ f(\lfloor \frac{x}{2} \rfloor + \delta_x, \lfloor \frac{y}{2} \rfloor + \delta_y) + f(\lceil \frac{x}{2} \rceil - \delta_x, \lceil \frac{y}{2} \rceil - \delta_y) \}$

#include <bits/stdc++.h>
using namespace std;

const long long INF = 4e18;
const int MAX_LENGTH = 10;
long long one_vec[MAX_LENGTH + 1][MAX_LENGTH + 1];
unordered_map <long long, long long> dp;
const int MAX_X = 1000000001;

long long DP(long long x, long long y){
    long long pos = x * MAX_X + y;
    if(dp.count(pos)) return dp[pos];

    long long tmp = INF;
    if(x <= MAX_LENGTH && y <= MAX_LENGTH) tmp = one_vec[x][y];

    for (long long dx = -MAX_LENGTH; dx <= MAX_LENGTH; dx++){
        for (long long dy = -MAX_LENGTH; dy <= MAX_LENGTH; dy++){
            long long x1 = x / 2 + dx, y1 = y / 2 + dy;
            long long x2 = x - x1, y2 = y - y1;
            if(min({x1, x2, y1, y2}) < 0) continue;
            if(x1 + y1 == 0 || x2 + y2 == 0) continue;
            tmp = min(tmp, DP(x1, y1) + DP(x2, y2));
        }
    }
    return dp[pos] = tmp;
}

int main(){
    int N; long long x, y;
    cin >> N >> x >> y;
    for (int i = 0; i <= MAX_LENGTH; i++)
        for (int j = 0; j <= MAX_LENGTH; j++) one_vec[i][j] = INF;

    for (int a, b, c; N--;){
        cin >> a >> b >> c;
        one_vec[a][b] = min(one_vec[a][b], (long long)c);
    }
    long long ans = DP(x, y);
    if(ans >= INF) cout << "-1\n";
    else cout << ans << '\n';
    return 0;
}

解法 2：基底 + 小范围微调

核心逻辑：我们先在原点附近进行小范围的精确搜索（微调），然后通过解二元一次方程组，利用“性价比”最高的基底向量组快速跨越远距离。

#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const ll INF = 4e18;

struct vec { int a, b; ll c; } v[105];
struct node {
    int x, y; ll d;
    bool operator > (const node& o) const { return d > o.d; }
};

int n; ll tx, ty, res = INF;
ll dp[205][205];

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> tx >> ty;
    for(int i = 1; i <= n; i++) cin >> v[i].a >> v[i].b >> v[i].c;
    
    for(int i = 0; i <= 30; i++)
        for(int j = 0; j <= 30; j++) dp[i][j] = INF;

    priority_queue<node, vector<node>, greater<node>> pq;
    dp[0][0] = 0; pq.push({0, 0, 0});
    while(!pq.empty()){
        node cur = pq.top(); pq.pop();
        if(cur.d > dp[cur.x][cur.y]) continue;
        for(int i = 1; i <= n; i++){
            int nx = cur.x + v[i].a, ny = cur.y + v[i].b;
            if(nx <= 30 && ny <= 30 && dp[nx][ny] > cur.d + v[i].c){
                dp[nx][ny] = cur.d + v[i].c;
                pq.push({nx, ny, dp[nx][ny]});
            }
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j++){
            ll det = 1LL * v[i].a * v[j].b - 1LL * v[j].a * v[i].b;
            for(int dx = 0; dx <= 30; dx++){
                for(int dy = 0; dy <= 30; dy++){
                    if(dp[dx][dy] == INF) continue;
                    ll rx = tx - dx, ry = ty - dy;
                    if(rx < 0 || ry < 0) continue;
                    if(det != 0){
                        ll na = rx * v[j].b - ry * v[j].a;
                        ll nb = ry * v[i].a - rx * v[i].b;
                        ll d = det;
                        if(d < 0) { d = -d; na = -na; nb = -nb; }
                        if(na >= 0 && nb >= 0 && na % d == 0 && nb % d == 0)
                            res = min(res, dp[dx][dy] + (na / d) * v[i].c + (nb / d) * v[j].c);
                    } else if(1LL * v[i].a * ry == 1LL * v[i].b * rx){
                        ll k = -1;
                        if(v[i].a != 0 && rx % v[i].a == 0) k = rx / v[i].a;
                        else if(v[i].b != 0 && ry % v[i].b == 0) k = ry / v[i].b;
                        else if(v[i].a == 0 && v[i].b == 0 && rx == 0 && ry == 0) k = 0;
                        if(k >= 0) res = min(res, dp[dx][dy] + k * v[i].c);
                    }
                }
            }
        }
    }
    if(res >= INF) cout << -1 << '\n';
    else cout << res << '\n';
    return 0;
}