uva10201 - Adventures in Moving - Part IV(01背包)

题目:uva10201 - Adventures in Moving - Part IV(01背包)

题目大意:一辆车要走D距离,然后它有个200L油箱,并且一开始有100L,现在给你一路上你会遇到的加油站,和这个加油站每升油的价钱,要求你最后到终点的时候油需要大于等于100L,问你加油最少的费用。如果到达不了目标地点就输出Impossible。

解题思路:首先要先到达这个加油站,然后就相当这个加油站你选不选择加油,选择加油了那么又要加多少油。dp【j】【i】代表到达第i个加油站还有jL油,dp【j】【i】 = MIn(dp【j +d【i】【l】】【l】);d【i】【l】代表第i个加油站和第l个加油站的距离,意思就是看当到达这个加油站,应该是从哪个加油站加了油出发这样花费最少。然后就是在这个加油站加多少的油的问题。

都是从0出发到达D这个位置,那么就在这两个位置加上加油站,然后用price来表示这个加油站是否真是存在。真实存在才可以加油。初始条件dp【0】【100】 = 0;

代码:

#include <cstdio>
#include <cstring>

const int N = 205;
const int INF = 0x3f3f3f3f;

int n;
int gas[N][2];
int f[N][N];
int d[N][N];
char str[N];

int Min (const int a, const int b) { return a < b ? a: b; }

void init () {

	for (int i = 0; i < n; i++)
		for (int j = i; j < n; j++)
			d[i][j] = gas[j][0] - gas[i][0];

	for (int i = 0; i < n; i++)
		for (int j = 0; j <= 200; j++)
			f[i][j] = INF;
	f[0][100] = 0;
}

int main () {

	int t;
	int D;
	scanf ("%d", &t);
	while (t--) {

		scanf ("%d%*c", &D);
		n = 1;
		gas[0][0] = 0;
		while (gets(str) != NULL && str[0] != '\0') {

			sscanf (str,"%d%d", &gas[n][0], &gas[n][1]);
			n++;
		}
/*		for (int i = 0; i < n; i++)
			printf ("%d %d\n", gas[i][0], gas[i][1]);*/
		if (gas[n - 1][0] != D) {

			gas[n][0] = D;
			gas[n][1] = 0;
			n++;
		}

		init();
		for (int i = 1; i < n; i++) {
			for (int j = 0; j <= 200; j++) {

				for (int l = i - 1; l >= 0; l--) { //哪种方式到达最省
					if (j + d[l][i] <= 200)
						f[i][j] = Min (f[i][j], f[l][j + d[l][i]]);
					else
						break;
				}
				if (gas[i][1] && f[i][j] != INF) {//加多少油(前提能够到达,并且这个加油站是真的)
					for (int k = j + 1; k <= 200; k++)
						f[i][k] = f[i][j] + (k - j) * gas[i][1];
				}
			}
		}

		int ans = INF;
		for (int i = 100; i <= 200; i++)
			ans = Min (ans, f[n - 1][i]);
		if (ans != INF)
			printf ("%d\n", ans);
		else
			printf ("Impossible\n");
		if (t)
			printf ("\n");
	}
	return 0;
}
时间: 08-21

uva10201 - Adventures in Moving - Part IV(01背包)的相关文章

uva 10201 Adventures in Moving - Part IV (DP)

uva 10201 Adventures in Moving - Part IV 题目大意:借了一辆车,车里有100单位的油.要到达N米外的目的地(每走一米消耗一个单位的油),在这一段路程中,有若干个加油站,给出的数据是每个加油站的位置和加一单位油的价格.要求到达目的地且剩下100单位油的最小消费.(到达不了则输出Impossible) 解题思路:dp[i][j]数组代表的是第i个加油站油量为j的最小费用. 状态转移方程: dp[i][j]=min(dp[i][j],dp[i?1][j+(mil

UVa 10201 Adventures in Moving - Part IV

https://vjudge.net/problem/UVA-10201 题意: 给出到达终点的距离和每个加油站的距离和油费,初始油箱里有100升油,计算到达终点时油箱内剩100升油所需的最少花费. 思路: 我们用d[i][j]来表示车子在第 i 个加油站时还剩 j 升油量的最小花费. 先说一下转移方程吧,d[i][j] = min(d[i][j], d[i - 1][j + l - k] + k*b[i]),k代表的是在 i 这个加油站所加的油量,加了之后的总油量就是 j . 需要注意的是,油

FZU 2214 Knapsack problem (01背包)

题意:给你n种物品,每种只有一个,第i种物品的价值为Vi,重量为Wi,把这些物品放入一个重量限制为B的背包中,使得背包内的物品在重量不超过B的前提下,价值尽量大,输出最大价值 1 <= n <= 500 1 <= B, w[i] <= 1000000000 1 <= v[1]+v[2]+...+v[n] <= 5000 思路:我们从范围中可以看到这个物品的重量和背包所能承受的重量特别大,我们不能使用常规的01背包,我们可以把问题转化一下,我们定义d(i,j)是把第i个物

bzoj1004: [HNOI2008]Cards Burnside引理+01背包

三维01背包算出在每一个置换下不变的染色方案数,Burnside引理计算答案. PS:数据太水所以只算恒等置换也是可以过的. #include<bits/stdc++.h> using namespace std; int n,m,p,x,y,z; bool u[61]; int f[21][21][21],s[61],v[61]; int power(int u,int v){ int d=1; for(;v;v>>=1){ if(v&1) d=d*u%p; u=u*u%

POJ 2184 01背包+负数处理

Cow Exhibition Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 10200   Accepted: 3977 Description "Fat and docile, big and dumb, they look so stupid, they aren't much fun..." - Cows with Guns by Dana Lyons The cows want to prove to

01背包//简直要被这道题玩死(掀桌)

先上链接: 表格什么的最清楚了:http://blog.csdn.net/mu399/article/details/7722810 dd大大的背包九讲: —————————————————— 01背包的状态转换方程 f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ),  f[i-1,j] } f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中,可以取得的最大价值. Pi表示第i件物品的价值. 决策:为了背包中物品总价值最大化,第 i件物品应该放入背包中

【背包问题】0-1背包、完全背包、多重背包、混合三种背包、二位费用背包、分组背包

一.0-1背包问题 输入:第一行物品的个数n,第二行背包的质量m,随后n行每行给出每个物品的重量和价值,每种物品只有一个. 输出:背包可以达到的最大价值 样例输入: 5 10 1 5 2 4 3 3 4 2 5 1 样例输出: 14 动态规划的过程中需要逆序,因为如果不是逆序那么 当i=0的时候 f[0]=0; f[1]=max(f[1],f[1-w[0]]+v[0])=5; f[2]=max(f[2],f[2-w[0]]+v[0])=10; f[3]=max(f[3],f[3-w[0]]+v[

HIT1485 A Good Helper(0-1背包)

终于补完第二次期末考了--果然考场上心态不好导致好多会做的题都没时间写 题目链接: http://acm.hit.edu.cn/hoj/problem/view?id=1485 题目描述: A Good Helper Submitted : 713, Accepted : 320 Abraham and Calford are Moving their things from dormitory A11 to A9,and they have their own carry limit,they

POJ 2923 【01背包+状态压缩/状压DP】

题目链接 Emma and Eric are moving to their new house they bought after returning from their honeymoon. Fortunately, they have a few friends helping them relocate. To move the furniture, they only have two compact cars, which complicates everything a bit.