ABC 320 F

题意

汽车从0开始出发，最终到达\(X_n\)再返程回到0，一开始有汽油\(H\)升，每公里耗油一升，在点\(X_i\)有加油站，每个加油站只可以加油一次，并且一次就加\(W_i\)升，花费\(P_i\)，且最大油量有限制\(\leq H\)。问最小花费

思路

它的数据范围\(n,H\leq 300\)，暴力dp，设状态\(dp_{i,j,k}\)为在站点\(i\)出发时油量为\(j\),返程回到站点\(i\)时油量为\(k\)，可以滚动优化掉一维，时间复杂度为\(O(nH^2)\)

状态转移方程

假设停在点i，有两种决策，在该点加油或不加
不加的话为

\[dp_{i+1,j-dis,k+dis} = dp_{i,j,k} \]

去的时候，加油为

\[dp_{i+1,j-dis+W_i,k+dis} = dp_{i,j,k}+P_i \]

回来的时候，加油为

\[dp_{i+1,j-dis,k+dis-W_i} = dp_{i,j,k}+P_i \]

其中\(dis\)为\(x_{i+1}-x_i\)，注意状态的合法范围，隐藏条件为\(dis\leq i\leq H\)，\(k\leq H-dis\)，想一下为什么

代码

void solve() 
{
	cin>>n>>h;
	for(int i=0;i<n;i++) 
	{
		cin>>x[i];
	}
	for(int i=0;i<n-1;i++) cin>>p[i]>>f[i];
	
	dp[h][0]=0;
	
	for(int it=0;it<n-1;it++) 
	{
		int dis = x[it]-(it==0?0:x[it-1]);
		memset(new_dp,0x3f,sizeof(new_dp));
		for(int i=0;i<=h;i++) 
		{
			for(int j=0;j<=h;j++) 
			{
				if(dp[i][j]==inf) continue;
				int ni=i-dis,nj=j+dis;
				if(ni>=0&&nj<=h) 
				{
					new_dp[ni][nj] = min(new_dp[ni][nj],dp[i][j]);
					new_dp[min(ni+f[it],h)][nj] = min(new_dp[min(ni+f[it],h)][nj],dp[i][j]+p[it]);
					new_dp[ni][max(nj-f[it],0ll)] = min(new_dp[ni][max(nj-f[it],0ll)],dp[i][j]+p[it]);
				}
			}
		}
		swap(dp,new_dp);
	}
	
	int dis = (x[n-1]-(n==1?0:x[n-2]))*2;
	
	int ans=inf;
	
	for(int i=0;i<=h;i++) 
	{
		for(int j=0;j<=h;j++) 
		{
			if(dp[i][j]==inf) continue;
			if(i-dis>=j) ans=min(ans,dp[i][j]);
		}
	}
	
	cout<<(ans==inf?-1:ans)<<endl;
}