题解 P1759 【通天之潜水】

· · 题解

看了看各位的题解，我的做法貌似是最简单实用的。 首先第一问，简单的01背包，在此不多加赘述 难就难在第二问：记录路径。这一点很多人都是用递归实现的，但我想到了一个更好的方法：用字符串； 众所周知，字符串是可以加减的，用法如下：

string a;
a+='a';
a+='b';
a+='c';
然后再输出a数组，就会发现是abc

回到这道题，我们可以发现，每一种状态都是由上一种状态转移过来的。

我们用ans[][]表示状态，则有ans[j][k]=ans[j-a[i]][k-b[i]]+char(i);

最后输出ans[m][v]即可；

上代码：

#include <iostream>
using namespace std;
long long m,v,n;
long long a[10001],b[10001],c[10001];
long long f[1001][1001];
string ans[1001][1001];
int main(){
    cin>>m>>v>>n;
    for(long long i=1;i<=n;i++){
        cin>>a[i]>>b[i]>>c[i];
    }
    for(long long i=1;i<=n;i++){
        for(long long j=m;j>=a[i];j--){
            for(long long k=v;k>=b[i];k--){
                if(f[j-a[i]][k-b[i]]+c[i]>f[j][k]){
                    f[j][k]=f[j-a[i]][k-b[i]]+c[i];
                    ans[j][k]=ans[j-a[i]][k-b[i]]+char(i);
                }
            }
        }
    }
    cout<<f[m][v]<<endl;
    for(long long i=0;i<ans[m][v].size();i++){
        long long temp=ans[m][v][i];
        cout<<temp<<" ";
    }
    cout<<endl;
    return 0;
}