ABC 320F Fuel Round Trip

题意
在坐标轴上给定N个点，坐标依次为x1,x2,...,xn,你需要从原点前往xn并且实现往返，其中从第一个点到第N-1个点上有加油站，其中第i个加油站可以花费p[i]购买f[i]升汽油，汽油的上限为H升，每行驶一单位距离需要花费一升汽油。在全部过程中每个加油站最多使用一次，判断是否可以完成行程并输出最小花费。(1<=N,H<=300)

思路
考虑dp，我们先把反向行驶的过程转化成正向行驶的过程。并设dp[i][j][k]为到达第i个站点，第一次经过时还持有j升油，第二次经过时还持有k升油时的最小花费。
那么假设下一站为第i+1个站点，那么从第i个站点到达第i+1个站点就有三种转移:

1. 第i个站点不选择加油
2. 第i个站点去程加油
3. 第i个站点返程加油

设dis为第i+1个站点与第i个站点的距离那么对应的状态转移方程就是:

1. dp[i+1][j-dis][k-dis]=min(dp[i+1][j-dis][k-dis],dp[i][j][k]),(j>=dis&&k>=dis)
2. dp[i+1][min(h,j+f[i])-dis][k-dis]=min(dp[i+1][min(h,j+f[i])-dis][k-dis],dp[i][j][k]+p[i]),(min(h,j+f[i])>=dis&&k>=dis)
3. dp[i+1][j-dis][min(k+f[i],h)-dis]=min(dp[i+1][j-dis][min(h,k+f[i])-dis],dp[i][j][k]+p[i]),
   (min(h,k+f[i])>=dis&&j>=dis)
   接下来我们要考虑一个细节：
   我们强行将返程的过程视为正向的过程，若我们去程到达xn时剩下的油量位h-i(即去程花费了i升油)，且我们在返程的过程中是将油量视为H开始的。那么返程时的油量j必须要保证大于或等于h-i，否则就无法到达。

代码

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int maxn=305;
int p[maxn],f[maxn],x[maxn];
int dp[maxn][maxn][maxn];
const int inf=1e9;

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	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];
	for(int i=0;i<maxn;i++) for(int j=0;j<maxn;j++) for(int k=0;k<maxn;k++) dp[i][j][k]=inf;
	dp[0][h][h]=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<=h;j++)
		  for(int k=0;k<=h;k++)
		  {
		  	 int dis=x[i+1]-x[i];
		  	 if(j>=dis&&k>=dis)
		  	   dp[i+1][j-dis][k-dis]=min(dp[i+1][j-dis][k-dis],dp[i][j][k]);
		  	 if(min(j+f[i],h)>=dis&&k>=dis)
		  	   dp[i+1][min(j+f[i],h)-dis][k-dis]=min(dp[i+1][min(j+f[i],h)-dis][k-dis],dp[i][j][k]+p[i]);
		  	 if(j>=dis&&min(h,k+f[i])>=dis)
		  	   dp[i+1][j-dis][min(h,k+f[i])-dis]=min(dp[i+1][j-dis][min(h,k+f[i])-dis],dp[i][j][k]+p[i]);
		  }
	}
	int ans=1e9;
	for(int i=0;i<=h;i++)
	  for(int j=0;j<=h;j++)
	    if(j>=h-i) ans=min(ans,dp[n][i][j]);
	if(ans==1e9) ans=-1;
	cout<<ans<<endl;
	
	return 0;
}