P14508 猜数游戏 guess

· · 题解

记 \max a_i=V。

目标位置在任何时刻，都一定是可能在一段区间内出现。

一开始是 [1,n]，当你走进这个区间的时候，就会把区间分成两部分，而目标必定在一部分里面。然后你会发现状态只跟区间长度有关，状态数 \Theta(n)，转移枚举走进去了多长（最多为 V），就好了。

还要跑个最短路，d_i 表示发生恰好 i 的位移最小代价是多少。这里只需要考虑 i \leq 2000 的情况就行了，因为有一个结论是：如果每一步大小都在 -S\sim S 之间，并且总和也在 -S \sim S 之间，那么总能够找到一种走路方法，使得走完每一步位置都在 -S \sim S 之间。

复杂度 \Theta(T(nV+V^2))。

#include <bits/stdc++.h>
#define int long long
#define FAST ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
/*
by qqqaaazzz
dis[i] 表示造成了 i 的真实位移的代价 
*/
int n,m;
int a[50010],b[50010];
int f[50010],g[50010];
int D[2010][2010];
int dis[2010];
bool vis[2010];
int is[2010];
int dp[50010];//dp[i] 表示还剩 i 个的时候呢？ 

void solve(){
    cin >> n >> m;
    for (int i=1;i<=m;i++) cin >> a[i];
    for (int i=1;i<=m;i++) cin >> b[i];
    memset(D,0x3f,sizeof(D));
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    for (int i=0;i<=2000;i++){
        for (int j=1;j<=m;j++){
            if(i+a[j]<=2000) D[i][i+a[j]] = min(D[i][i+a[j]],b[j]);
            if(abs(i-a[j])<=2000) D[i][abs(i-a[j])] = min(D[i][abs(i-a[j])],b[j]);
        }
    }
    //跑 Dij 
    dis[0] = 0;
    for (int i=0;i<=2000;i++){
        int k = -1;
        for (int j=0;j<=2000;j++){
            if(!vis[j]&&(k==-1||dis[j]<dis[k])) k = j;
        }
        vis[k] = 1;
        for (int j=0;j<=2000;j++){
            dis[j] = min(dis[j],dis[k]+D[k][j]);
        }
    }
    memset(dp,0x3f,sizeof(dp));
    dp[1] = 0;
    for (int i=2;i<=n;i++){
        for (int j=1;j<=min(i-1,2000ll);j++){
            dp[i] = min(dp[i],max(dp[j],dp[i-j])+dis[j]);
        }
    }
    cout << (dp[n]>1e18? -1:dp[n]) << "\n";
}

signed main()
{
    FAST;
    int c,t;
    cin >> c >> t;
    while(t--) solve();
    return 0;
}