luogu P1759 通天之潜水

题目背景

直达通天路·小A历险记第三篇

题目描述

在猴王的帮助下，小A终于走出了这篇荒山，却发现一条波涛汹涌的河拦在了自己的面前。河面上并没有船，但好在小A有n个潜水工具。由于他还要背重重的背包，所以他只能背m重的工具，又因为他的力气并不是无限的，河却很宽，所以他只能背有v阻力的工具。但是这条河下有非常重要的数据，所以他希望能够停留的时间最久。于是他找到了你，让你告诉他方案。

输入格式

三个数m,v,n如题目所说

接下来n行，每行三个数ai,bi,ci分别表示所含的重力，阻力，能够支撑的时间

输出格式

第一行一个数，表示最长的时间

接下来一行，若干个数，表示所选的物品

说明/提示

1<=m,v<=200,n<=100

数据保证一定有方案。

若有多种方案，输出前面尽量小的方案。

---

01背包附带两个限制条件

除此之外还要一点递归技巧来输出方案

让 f[i][j][k] 表示dp[i][j]转移时是否选择了k

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define int long long

using namespace std;

const int N=205;

int a[N],b[N],val[N];

int dp[N][N];

bool f[N][N][N];

void output(int i,int j,int k){

	if(i==1){

		if(f[i][j][k])printf("1 ");

		return;

	}

	if(f[i][j][k])output(i-1,j-a[i],k-b[i]);

	else output(i-1,j,k);

	if(f[i][j][k])printf("%d ",i);

}

signed main(){

	int m,v,n;

	cin>>m>>v>>n;

	for(int i=1;i<=n;i++)

	scanf("%lld%lld%lld",&a[i],&b[i],&val[i]);

	for(int i=1;i<=n;i++){

		for(int j=m;j>=a[i];j--)

		for(int k=v;k>=b[i];k--)

		if(dp[j][k]<dp[j-a[i]][k-b[i]]+val[i]){

			dp[j][k]=dp[j-a[i]][k-b[i]]+val[i];

			f[i][j][k]=1;

		}

	}

	cout<<dp[m][v]<<endl;

	output(n,m,v);

}