The 2022 Hangzhou Normal U Summer Trials

H. Optimal Biking Strategy

题目链接

题意：

有 n n n个自行车站在 a i a_i ai​处，但是你只能在车站选择骑或者停下自行车。有 k k k元钱，每元钱最多让你骑 s s s米。当前在起点0米处，你需要走到终点 p p p米处，求最小步行的距离。

思路：

很明显的dp,我们定义 d p i , j dp_{i, j} dpi,j​表示走到第 i i i个车站时花费 j j j元钱走的最短的步行距离。假设当前车站花费了 x x x元，那么我们应该贪心的从距离当前 a i a_i ai​距离不超过 x × s x \\times s x×s的尽量远的车站 a j a_j aj​,求该车站的位置可以二分求解。状态转移方程：
d p i , j = m i n ( d p i − 1 , j + a i − a i − 1 , d p i d x , j − x ) dp_{i,j} = min(dp_{i - 1,j} + a_i-a_{i-1}, dp_{idx, j-x}) dpi,j​=min(dpi−1,j​+ai​−ai−1​,dpidx,j−x​)

LL f[N][6];//f[i][j]表示到达第i个点花费j元骑行后的最小距离
void solve(){
    scanf(\"%d%d%d\", &n, &p, &s);
    for(int i = 1; i <= n; i++) scanf(\"%d\", &a[i]);
    scanf(\"%d\", &k);
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= k; j++){
            f[i][j] = INF;
        }
    }
    f[0][0] = f[0][1] = f[0][2] = f[0][3] = f[0][4] = f[0][5] = 0;
    for(int i = 1; i <= n; i++){
        f[i][0] = f[i - 1][0] + a[i] - a[i - 1];
        for(int j = 1; j <= k; j++){
            f[i][j] = f[i - 1][j] + a[i] - a[i - 1];
            for(int x = 0; x <= j; x++){
                int dis = x * s;
                int idx = -1, l = 1, r = i - 1;
                while(l <= r){
                    int mid = l + r >> 1;
                    if(a[i] - a[mid] <= dis){
                        idx = mid;
                        r = mid - 1;
                    } else l = mid + 1;
                }
                if(idx == -1) continue;
                else{
                    f[i][j] = min(f[i][j], f[idx][j - x]);
                }
            }
        }
    }
    LL ans = INF;
    for(int i = 1; i <= n; i++){
        ans = min(ans, f[i][k] + p - a[i]);
    }
    cout << ans << endl;
}

K. Klee’s Wonderful Adventure

题目链接

题意：

给定 n n n个点，和四个象限的速度，求两个点的最短到达时间

思路：

给定了距离和时间，那么我们可以求出每个点之间的时间，那么我们可以很显然的想到最短路问题。
直接使用 d i j k s t r a dijkstra dijkstra跑就行了。

int n, v1, v2, v3, v4, v0, s, t;
pii idx[N];
double dis[N][N];
bool vis[N];
double cal(int x, int y, int xx, int yy){
    double c = 1.0000000;
    return sqrt(1LL * (x - xx) * (x - xx) + (1LL * (y - yy) * (y - yy)));
}
int check(int x, int y){
   if(x >= 1 && y >= 1) return 1;
   if(x <= -1 && y >= 1) return 2;
   if(x <= -1 && y <= -1) return 3;
   if(x >= 1 && y <= -1) return 4;
   return 0;
}
double ans[N];
void solve(){                                       
    scanf(\"%d%d%d%d%d%d%d%d\", &n, &v1, &v2, &v3, &v4, &v0, &s, &t);
    for(int i = 1; i <= n; i++){
        int a, b;
        scanf(\"%d%d\", &a, &b);
        idx[i] = {a, b};
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(i == j) dis[i][j] = 0;
            else{
                double d = cal(idx[i].fi, idx[i].se, idx[j].fi, idx[j].se);
                int f1 = check(idx[i].fi, idx[i].se);
                int f2 = check(idx[j].fi, idx[j].se);
                if(f1 != f2) {
                    dis[i][j] = dis[j][i] = d / v0;
                    continue;
                }
                if(f1 == 1) {
                    dis[i][j] = dis[j][i] = d / v1;
                }else if(f1 == 2){
                    dis[i][j] = dis[j][i] = d / v2;
                }else if(f1 == 3){
                    dis[i][j] = dis[j][i] = d / v3;
                }else if(f1 == 4){
                    dis[i][j] = dis[j][i] = d / v4;
                }
            }
        }
    }
 
    for(int i = 1; i <= n; i++) ans[i] = INF;
    ans[s] = 0;
    for(int i = 0; i < n; i++){
        int t = -1;
        for(int j = 1; j <= n; j++){
            if(!vis[j] && (t == -1 || ans[t] > ans[j])){
                t = j;
            }
        }
        vis[t] = true;
        for(int i = 1; i <= n; i++){
            ans[i] = min(ans[i], ans[t] + dis[t][i]);
        }
    }
    printf(\"%.6lf\", ans[t]);
}