CF510D Fox And Jumping

xiezheyuan · 2022-10-04 14:04:57 · 题解

简要题意

给出 n 张卡片，分别有 l_i 和 c_i。在一条无限长的纸带上，你可以选择花 c_i 的钱来购买卡片 i，从此以后可以向左或向右跳 l_i 个单位。问你至少花多少元钱才能够跳到纸带上全部位置。若不可能，输出 -1。

1 \leq n \leq 300,1 \leq l_i \leq 10^{9},1 \leq c_i \leq 10^{5}

思路

首先，如果我们可以选出一些个卡片 (l_i,c_i)，使得全部的 c_i 互质（我的意思是 (c_i,(c_{i+1},(c_{i+2},\cdots))) = 1）。因为裴蜀定理 c_ix+c_jy=1 有解，所以一定可以从位置 x 跳到 x \pm 1。

一开始，我的思路是能选择 c = 1 就选择，否则选择两个不同的。Hack 数据：

7
15015 10010 6006 4290 2730 2310 1
1 1 1 1 1 1 10

答案应该是 6（选择前 6 个）。

然后我们考虑 DP，设 f_{i,j} 为选择前 i 个，选择的数的 \gcd 是 j 的最小代价。显然，最后答案是 f_{n,1}。动态转移方程：

无法通过本题，考虑优化。发现这个动态转移方程很像三角形不等式 \operatorname{dis}_{u}=\min(\operatorname{dis}_{u},\operatorname{dis}_{v}+W_{u,v})，想到用最短路优化。

使用堆优化 Dijkstra 算法可以做到 O(n^{3})，可以通过本题。

代码

```cpp
#include <bits/stdc++.h>
#define int long long
#define gcd __gcd
using namespace std;

unordered_map<int, int> dis;
unordered_set<int> vis;
priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > pq;
int n,l[305],c[305];

void dijkstra(){
    pq.push({0,0});
    dis[0]=0;
    while(!pq.empty()){
        int x = pq.top().second;
        pq.pop();
        if(x==1){
            break;
        }
        if(vis.find(x) != vis.end()){
            continue;
        }
        vis.insert(x);
        for(int j=1;j<=n;j++){
            int y = gcd(x,l[j]);
            if(dis.find(y) == dis.end()){
                dis[y] = INT_MAX;
            }
            if(dis[y]>dis[x]+c[j]){
                dis[y]=dis[x]+c[j];
                pq.push(make_pair(dis[y],y));
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>l[i];
    }
    for(int j=1;j<=n;j++){
        cin>>c[j];
    }
    dijkstra();
    if(dis.find(1)==dis.end()){
        // Impossible
        cout<<-1;
    }
    else{
        cout<<dis[1];
    }
    return 0;
}

AC Record