题解 P1759 【通天之潜水】
wjyyy
2018-04-30 09:53:14
乍一眼看上去，是一个简单的背包，再一看，原来有2个限制条件。因此我们的数组要开到3维（没有压维做起来比较方便），而且这个题最重要的是要输出路径，这样我们在普通的背包里要进行改进。
首先我们枚举的时候要用到两个参数，其他和01背包一样，并且枚举要从1开始~~（这里卡了我半天）~~。接着我们在更新的时候要存储路径，即$pre[i][j][k]$和$g[i][j][k]$，$pre$数组是存如果这个物品装入背包，那么背包的上一个物品的编号，$g$是存①如果这个物品装入背包，存储它的编号，②如果这个物品不装入背包，存储上一个物品的编号。
这样我们就完成了路径记录和背包过程，最后根据$pre$数组回溯找路径并倒序输出。回溯时也要注意，重力阻力减小了当前物品的值，但回溯时要调用减小前的值，所以加减顺序不要搞错了，这一点在代码里也有标注。
```cpp
#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;
}
```