P1759 通天之潜水（双写法+解析）

算法解析

动态规划问题满足三大重要性质

最优子结构性质：如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。

子问题重叠性质：子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

无后效性：将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。

P1759 通天之潜水

题目

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

输入

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

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

输出

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

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

样例

100 100 3                                       405

50 60 289                                       1 2

40 10 116

50 50 106

解析

刚开始看的时候还行，看到要输出所选的物品的时候呆了，想到两种方法

\(First\)是用f[i][j]算最大时间，用三维数组p[i][j][k]表示第\(i\)个物品在有\(j\)重力\(k\)阻力时是否选这个工具，顺着数组递归输出选的工具

\(Second\)是用DFS 应为数据比较小，不用剪枝也可以过

代码

//第一组

#include <bits/stdc++.h>

#define N 10005

using namespace std;

int f[N][N];

int w[N],v[N],t[N];

bool p[105][205][205];

void print(int date,int m,int s){

	if (date==1){

		if (p[date][m][s]==true)

			printf("1 ");

		return;

	}else if (p[date][m][s]==true){

		print(date-1,m-w[date],s-v[date]);

		printf("%d ",date);

	}else {

		print(date-1,m,s);

	}return;

}

int main(){

	int m,s,n;

	scanf("%d%d%d",&m,&s,&n);

	f[0][0]=0;

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

		scanf("%d%d%d",&w[i],&v[i],&t[i]);

	}

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

		for (int i=m;i>=w[l];i--){

			for (int j=s;j>=v[l];j--){

				if (f[i][j]<f[i-w[l]][j-v[l]]+t[l]){

					f[i][j]=f[i-w[l]][j-v[l]]+t[l];

					p[l][i][j]=true;

				}

			}

		}

	}

	printf("%d\n",f[m][s]);

	print(n,m,s);

	return 0;

}

———————————————————————————一点也不美丽的华丽分割线———————————————————————————————

//第二个

#include <bits/stdc++.h>

using namespace std;

int m,v,n,a[105],b[105],c[105];

int ans,r[105],cs[105],cho;

void dfs(int Nans,int date,int m,int v,int h){

	if (m<0||v<0)return;

	if (Nans>ans){

		ans=Nans;cho=h;

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

			r[i]=cs[i];

	}

        if (date>n)return;//当date==n+1时r[i]还没有把cs[i]的都记录下来，要等记录完在return，所以放到下面

	cs[h+1]=date;

	dfs(Nans+c[date],date+1,m-a[date],v-b[date],h+1);

	dfs(Nans,date+1,m,v,h);

	return;

}

int main(){

	scanf("%d%d%d",&m,&v,&n);

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

		scanf("%d%d%d",&a[i],&b[i],&c[i]);

	}

	dfs(0,1,m,v,0);

	printf("%d\n",ans);

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

		printf("%d ",r[i]);

	return 0;

}

巴特西

P1759 通天之潜水（双写法+解析）

算法解析

P1759 通天之潜水

题目

输入

输出

样例

解析

代码

最新文章

热门文章