题解 P1759 【通天之潜水】

这道题是一个简单的二维背包问题,以重力、阻力为代价,以时间为价值,做二维背包,但是这道题的重点是我们要输出路径,而且是前面尽量小的方案(即路径)

所以,我们用一个伴随的三维数组来解决这个问题,当更新反f[i][j]时,我们顺便把路径更新;

kk[i][j][k] //重力为i,阻力为j时,第k个物品;

#include<iostream>
#include<cstdio>
#define II int
#define R register
#define I 3456
using namespace std;

II f[I][I],a[I],b[I],c[I],kk[230][230][230];

II m,n,v;

int main()
{
    scanf("%d%d%d",&m,&v,&n);
    for(R II i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);
    for(R II i=1;i<=n;i++)
    {
        for(R II j=m;j>=a[i];j--)
        {
            for(R II l=v;l>=b[i];l--)
            {
                // f[j][l]=max(f[j][l],f[j-a[i]][l-b[i]]+c[i]);
                if(f[j][l]<f[j-a[i]][l-b[i]]+c[i]){
                    f[j][l]=f[j-a[i]][l-b[i]]+c[i];
                    for(R II k=1;k<=kk[j-a[i]][l-b[i]][0];k++)
                    {
                        kk[j][l][k]=kk[j-a[i]][l-b[i]][k];
                    }
                    kk[j][l][0]=kk[j-a[i]][l-b[i]][0]+1;
                    kk[j][l][kk[j][l][0]]=i;
                }
            }
        }
    }
    cout<<f[m][v]<<'\n';
    for(R II i=1;i<=kk[m][v][0];i++) printf("%d ",kk[m][v][i]);
    return 0;
}

发表于 2017-08-01 13:58:09 in 题解