题解：P1359 租用游艇

Backpack_dp · 2026-01-20 23:20:57 · 题解

观察到 n\le 200，如果你套 200 层循环肯定过不了 （应该不会有人向我一样傻到这么想吧)

题目要我们求从 1 到 n 的最小费用方案，于是考虑贪心，每次只去到费用最小的出租站。

当然很明显这是不可行的，很容易找出反例：

3
5 6
8

如果使用贪心的话则你的代码会输出 13，而事实是你只需要 6 块钱就可以游玩全程（肯定不会有人这样买票吧）。

贪心不行我们就可以考虑 dp。

我们可以设 dp_{i,j} 表示从 i 到 j 的最小费用。

可以很容易推出式子：

最终的结果就是 dp_{1,n}。

signed main(){
    cin>>n;
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            cin>>dis[i][j];
      dp[i][j]=dis[i][j];
        }
    }
    dp[1][1]=0;
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            for(int x=i;x<=j;x++){
                dp[i][j]=min(dp[i][j],dp[i][x]+dp[x][j]);
            }
        }
    }
    cout<<dp[1][n];
    return 0;
}

然额 O(n^3) 的时间还是太给力了，我们假设 n\le10^4 那么此时肯定通过不了。

又观察发现题目中两两之间的费用在上述方法里利用率极低（除了当最大值没有任何用处），于是我们可以尝试压缩维度。

我们直接设 dp_i 表示从 1 到 i 的最小费用。

于是尝试推写状态转移方程。

其中 dis_{i,j} 表示 i 到 j 的费用。

这个时候我们就成功将 n^3 的时间压缩到了 n^2！！

signed main(){
    cin>>n;
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            cin>>mp[i][j];
        }
        dp[i]=114514;
    }
    dp[n]=114514;
    dp[1]=0;
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;j++){
            dp[i]=min(dp[i],dp[j]+mp[j][i]);
        }
    }

    cout<<dp[n];
    return 0;
}

以上就是本题解的全部内容，还望 dalao 们 点一个赞，谢谢。

蒟蒻的第一篇 dp 题解，求过。