P1759

· · 题解

题目传送门：P1759 通天之潜水。

2025/10/21 更新：正好今天我们没什么事干，把以前的题解写更好点。

Part 1：

这是一道动态规划的题目，既然是动态规划，那么就要弄清楚状态，状态转移公式。

从题目中可以看出，这是一道背包问题。那么既然知道了是背包问题，那么状态和状态转移公式就很容易得出了。首先是状态，对于 f_{i,j}，表示重量为 i，阻力为 j 的能够获得的最大价值。其次，就是状态转移公式，根据背包问题的公式，可以得出：

f_{i,j}=\max(f_{i,j},f_{i-m,j-v}+w)

其中，v 代表这件物品的阻力，m 代表这件物品的重量，w 代表这件物品的价值。

确定好状态和状态转移公式，还要确定怎么记录使用的工具有哪些。我使用的方法是用二维字符串数组来记录，当当前的最高价值要更新时，这个字符串数组的对应字符串也要跟着更新。

弄清楚以上代码后，就可以轻松的打出代码： :::info[Code.]

#include <bits/stdc++.h>//万能头文件。
using namespace std;
long long n,m,v,dp[1005][1005];//定义背包数组。
string ans[1005][1005];//定义字符串二维数组。
struct wbx{
    long long a,b,c;
}a[1005];//每一个工具都用结构体记录。
int main(){
    cin>>m>>v>>n;//输入变量。
    for(int i=1;i<=n;i++) cin>>a[i].a>>a[i].b>>a[i].c;//输入每一个工具对应的数值。
    for(int i=1;i<=n;i++)
        for(int j=m;j>=a[i].a;j--)
            for(int k=v;k>=a[i].b;k--)
                        //如果用现在可以的阻力和重量分别减少这个工具所产生的价值大于原来的价值，那么就应该更新这个最大价值。
                if(dp[j-a[i].a][k-a[i].b]+a[i].c>dp[j][k])
                    dp[j][k]=dp[j-a[i].a][k-a[i].b]+a[i].c,ans[j][k]=ans[j-a[i].a][k-a[i].b]+char(i);
                            //状态转移公式
    cout<<dp[m][v]<<endl;//输出最大价值。
    for(int i=0;i<ans[m][v].size();i++) cout<<int(ans[m][v][i])<<" ";//输出答案。
    return 0;
}

:::

Part 2：

但是在添加了能够 Hack 掉所有题解的数据，怎么可能这么容易让你对？

我一开始也是被 Hack 掉了，在仔细的读题之后，发现，我一直都省略掉了一句话：若有多种方案，输出前面尽量小的方案。

在讨论版找到了 Hack 数据后，我发现我就是错了这一个地方。 那么要怎么办呢？可以在判断条件中加入一个：如果价值相等，那么就挑选字典序更小的那一个。这样子，就可以 AC 了。 :::info[Code.]


#include <bits/stdc++.h>
using namespace std;
long long n,m,v,dp[1005][1005];
string ans[1005][1005];
struct wbx{
    long long a,b,c,t;
}a[1005];
int main(){
    cin>>m>>v>>n;
    for(int i=1;i<=n;i++) cin>>a[i].a>>a[i].b>>a[i].c,a[i].t=i;
    for(int i=1;i<=n;i++)
        for(int j=m;j>=a[i].a;j--)
            for(int k=v;k>=a[i].b;k--)
            {
                if(dp[j-a[i].a][k-a[i].b]+a[i].c>dp[j][k] || dp[j-a[i].a][k-a[i].b]+a[i].c==dp[j][k] && ans[j-a[i].a][k-a[i].b]+char(a[i].t)<ans[j][k])
                dp[j][k]=dp[j-a[i].a][k-a[i].b]+a[i].c,ans[j][k]=ans[j-a[i].a][k-a[i].b]+char(a[i].t);
            }

    cout<<dp[m][v]<<endl;
    for(int i=0;i<ans[m][v].size();i++) cout<<int(ans[m][v][i])<<" ";
    return 0;
}
:::
谢谢！