// [解题方法]
// dp[i][j]表示到达第i个加油站剩余油量为j时的最小花费
// 特殊地,dp[n][j]表示到达终点剩余油量为j时的最小花费
// 状态转移:(设w[i]为每个加油站的位置,p[i]为油单价)
// 行驶:dp[i][j-(w[i]-w[i-1])] = dp[i-1][j](0<i<=n)
// 加油:dp[i][j] = dp[i][j-1]+p[i](0<i<n)因为n是特意增加的终点,不是加油站
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
#define LL long long
#define N 105
#define M 205
#define inf 0x3fffffff
int dp[N][M], w[M], p[M];
int main()
{
char s[105];
int t, n, i, j, l, m = 200;
cin >> t;
getchar();
while (t--)
{
cin >> l;
getchar();
n = 1;
w[0] = 0;
while (gets(s))
{
if (s[0] == 0) break;
sscanf (s, "%d%d", w+n, p+n);
++n;
}
w[n] = l;
for (i = 0; i <= n; i++)
for (j = 0; j <= m; j++)
dp[i][j] = inf;
dp[0][100] = 0;
for (i = 1; i <= n; i++)
{
for (j = w[i]-w[i-1]; j <= m; j++)
dp[i][j-(w[i]-w[i-1])] = dp[i-1][j];
if (i < n) for (j = 1; j <= m; j++)
dp[i][j] = min(dp[i][j], dp[i][j-1]+p[i]);
}
int mins = dp[n][100];
for (j = 101; j <= m; j++)
if (mins > dp[n][j])
mins = dp[n][j];
if (mins == inf) puts ("Impossible");
else cout << mins << endl;
if (t) puts ("");
}
return 0;
}
分享到:
相关推荐
adventures-in-ml-code, 这个存储库保存了站点http的所有代码 adventures-in-ml-code这个存储库保存了站点 http://www.adventuresinmachinelearning.com的所有代码。这是 neural_network_tutorial.py 开发的代码,它
us-17-Borgaonkar-New-Adventures-In-Spying-3G-And-4G-Users-Locate-Track-And-Monitor
藏经阁-Adventures-In-Attacking-Wind-Farm-Control-Networks.pdf
Borgaonkar-New-Adventures-In-Spying-3G-And-4G-Users-Locate-Track-And-Monitor
藏经阁-The-Adventures-Of-Av-And-The-Leaky-Sandbox.pdf
九上牛津版-Unit7-The-Adventures-of-Tom-Sawyer同步练习及答案.doc
Adventures-in-Phandalin
T-rex-Adventures-3D-Game
Sidney的经典教材Adventures in Stochastic Processes,适合有很强数学或概率基础的人学习
Adventures in Minecraft英文版
画布上的新冒险玩画布...
Adventures in Stochastic Processes (Sidney Resnick)英文原版 随机过程经典读物
这是我的博客的仓库
Vim历险记 一个专门致力于真正编辑的网站: 。 执照
ml历险记 该存储库包含该网站的所有代码 neuro_network_tutorial.py是开发的代码tensor_flow_tutorial.py是开发的代码convolutional_neural_network_tutorial.py是 keras_cnn.py中的开发的代码。...
深度学习历险记深度学习出版物,框架和资源概述深度卷积神经网络在大规模图像和视频识别方面取得了一系列突破。 该存储库旨在提供自2013年以来深度学习领域最新作品的详尽清单。 这将是一个不断发展的存储库,我将...
Adventures in Raspberry Pi (3 edition), 数字版。
经典英文数学教材 数学专业研究生用书 南开大学数学院 随机过程课程教材之一