题解 P1759 【通天之潜水】

2018-04-30 09:53:14


乍一眼看上去,是一个简单的背包,再一看,原来有2个限制条件。因此我们的数组要开到3维(没有压维做起来比较方便),而且这个题最重要的是要输出路径,这样我们在普通的背包里要进行改进。

首先我们枚举的时候要用到两个参数,其他和01背包一样,并且枚举要从1开始(这里卡了我半天)。接着我们在更新的时候要存储路径,即$pre[i][j][k]$和$g[i][j][k]$,$pre$数组是存如果这个物品装入背包,那么背包的上一个物品的编号,$g$是存①如果这个物品装入背包,存储它的编号,②如果这个物品不装入背包,存储上一个物品的编号。

这样我们就完成了路径记录和背包过程,最后根据$pre$数组回溯找路径并倒序输出。回溯时也要注意,重力阻力减小了当前物品的值,但回溯时要调用减小前的值,所以加减顺序不要搞错了,这一点在代码里也有标注。

#include<cstdio>
#include<cstring>
int f[101][201][201];
int g[101][201][201];
int pre[101][201][201];
int r[101],p[101],t[101];
int main()
{
    memset(f,0,sizeof(f));
    memset(pre,0,sizeof(pre));
    int m,v,n;
    scanf("%d%d%d",&m,&v,&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&r[i],&p[i],&t[i]);
        for(int j=0;j<=m;j++)
            for(int k=0;k<=v;k++)
            {
                if(j<r[i]||k<p[i]||f[i-1][j][k]>=f[i-1][j-r[i]][k-p[i]]+t[i])
                {
                    f[i][j][k]=f[i-1][j][k];
                    g[i][j][k]=g[i-1][j][k];
                }
                else
                {
                    f[i][j][k]=f[i-1][j-r[i]][k-p[i]]+t[i];
                    pre[i][j][k]=g[i-1][j-r[i]][k-p[i]];
                    g[i][j][k]=i;
                }
            }
    }
    printf("%d\n",f[n][m][v]);
    int x=g[n][m][v],cnt=0;
    int a[101];
    int u;
    while(pre[x][m][v]!=0)
    {
        a[++cnt]=x;
        x=pre[x][m][v];//回溯调用的是包含当前物品的
        m-=r[a[cnt]];//回溯后所用的是不含当前物品的
        v-=p[a[cnt]];
    }
    a[++cnt]=x;//模拟栈倒序输出
    for(int i=cnt;i>=1;i--)
        printf("%d ",a[i]);
    return 0;
}