题目
F - Fuel Round Trip
总结
- 关键在于状态的定义。因为每个位置尽可加油一次,因此往返会相互影响,因而必须考考虑状态中定义
去时经过此地的油量j
与回时经过此地的油量k
,这样才能成功转移;
- 此外,本题状态转移比较奇特,相邻两个位置的状态的转移,在时间上包含去和回两个不同的时刻,较难理解。
- 最后,dp完毕,求
ans
时注意到不能仅遍历dp[n][i][i]
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
using LL = long long;
const int N = 310, INF = 0x3f3f3f3f;
int dp[N][N][N];
int x[N], p[N], f[N];
void solv()
{
int n, h;
cin >> n >> h;
for (int i = 1; i <= n; i ++)
cin >> x[i];
for (int i = 1; i <= n-1; i ++)
cin >> p[i] >> f[i];
memset(dp, 0x3f, sizeof dp);
// 定义dp[i][j][k]
// 考虑走完前i个位置,
// 去时经过此位置时的油量为j,
// 回时经过此位置时油量为k,
// 的最小花费
// (这里jk油量指的是在位置i加油后的油量(如果选择加油))
for (int i = 0; i <= h; i ++)
dp[0][h][i] = 0;
for (int i = 1; i <= n; i ++)
{
int d = x[i] - x[i - 1];
for (int j = 0; j <= h; j ++)
for (int k = 0; k <= h; k ++)
{
if (j < d || k + d > h)
continue;
// 1. 往返在第i个位置都没有加油
dp[i][j - d][k + d] = min(dp[i][j - d][k + d], dp[i - 1][j][k]);
// 2. 正向走的时候在i加油
dp[i][min(h, j - d + f[i])][k + d] = min(dp[i][min(h, j - d + f[i])][k + d], dp[i - 1][j][k] + p[i]);
// 3. 反向走回来时在i加油
dp[i][j - d][max(0, k + d - f[i])] = min(dp[i][j - d][max(0, k + d - f[i])], dp[i - 1][j][k] + p[i]);
}
}
int ans = INF;
// 这里不能仅遍历 dp[n][i][i]
// 因为dp过程中涉及到油量容量的边界处理,
// 其中并不是准确的转移,存在取 min 和 max的情况
// 因而最终在目的地并不一定去与回油量相等
// 但是不能莫名增加油量
for (int i = 0; i <= h; i ++)
for (int j = 0; j <= i; j ++)
ans = min(ans, dp[n][i][j]);
cout << (ans == INF ? -1 : ans) << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
while (T--)
solv();
return 0;
}