首页 / 算法 / BZOJ 2072 POI2004 MOS 动态规划+贪心

BZOJ 2072 POI2004 MOS 动态规划+贪心

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了BZOJ 2072 POI2004 MOS 动态规划+贪心，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含736字，纯文字阅读大概需要2分钟。

内容图文

题目大意：过桥问题

我们考虑利用时间最小的两个人倒运，把时间大的人依次送过去

有两种方式：

1.时间最小的人和时间最大的人过去，然后时间最小的人把火把拿回来

2.时间最小和第二小的两个人过去，然后时间最小的人把火把拿回来；接着时间最大和第二大的两个人过去，时间第二小的人把火把拿回来

为了保证最优 运输应该不外乎这两种形式

那么令f[i]表示当前没有过桥的人还剩i个时的最短时间 DP即可

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 100100
using namespace std;
int n,a[M];
long long f[M];
int main()
{
	int i;
	cin>>n;
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	if(n<=2) return cout<<a[n]<<endl,0;
	for(i=n-1;i>=2;i--)
	{
		f[i]=f[i+1]+a[1]+a[i+1];
		if(i<=n-2)
			f[i]=min(f[i],f[i+2]+a[2]+a[1]+a[i+2]+a[2]);
	}
	cout<<f[2]+a[2]<<endl;
	return 0;
}


原文：http://blog.csdn.net/popoqqq/article/details/44154629

内容总结

以上是互联网集市为您收集整理的BZOJ 2072 POI2004 MOS 动态规划+贪心全部内容，希望文章能够帮你解决BZOJ 2072 POI2004 MOS 动态规划+贪心所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1262668.html

来源：【匿名】