UVA - 10201 Adventures in Moving - Part IV

本文主要是介绍UVA - 10201 Adventures in Moving - Part IV，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：在100升为初始的车，求到达终点的最小花费，路上有加油站，分别给你离起点的距离和每升油的价格，没升油走一公里，在选与不选做动态规划

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN = 205;
const int INF = 1<<29;int n,dp[MAXN][MAXN],d[MAXN],p[MAXN];
char str[MAXN];int main(){int t;scanf("%d",&t);while (t--){int num = 1;scanf("%d%*c",&n);while (gets(str) && str[0] != '\0'){sscanf(str,"%d%d",&d[num],&p[num]);++num;}num--;dp[0][100] = 0,d[0] = 0;for (int i = 0; i <= num; i++)for (int j = 0; j <= 200; j++)dp[i][j] = INF;dp[0][100] = 0;for (int i = 1; i <= num; i++){int dis = d[i] - d[i-1];for (int j = 0; j <= 200; j++){if (j+dis <= 200)dp[i][j] = dp[i-1][j+dis];for (int k = 0; k <= j; k++)if (j+dis-k <= 200 && dp[i-1][j+dis-k] != EOF)dp[i][j] = min(dp[i][j],dp[i-1][j+dis-k]+k*p[i]);}}if (100+n-d[num] <= 200 && dp[num][100+n-d[num]] != INF)printf("%d\n",dp[num][100+n-d[num]]);else printf("Impossible\n");if (t)printf("\n");}return 0;
}

这篇关于UVA - 10201 Adventures in Moving - Part IV的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---