暴力部分

$n\leq 8$：

我们直接$dfs$在每个位置，要么把油加满，要么把油加到可以去某一个后面的加油站的量，然后继续$dfs$即可。其实不好想到。之所以给$8$是因为原题范围就是$8$。

$n\leq 100,C\leq 1000$：

$dp_{i,j}$表示走到$i$，有$j$的油的最小代价即可，$nC^2$复杂度。

$n\leq 1000,C\leq 10000$：

我们转移的时候在同一层，当完全背包来转移即可。

memset(dp,-1,sizeof(dp));
for (int i=1;i<=C;i++) dp[1][i]=p[1]*i;
for (int i=1;i<=n;i++)
{
    for (int j=0;j<=C;j++)
        if (dp[i][j]!=-1)
        {
            MIN(dp[i][j+1],dp[i][j]+p[i]);
        }
    for (int j=x[i];j<=C;j++)
        if (dp[i][j]!=-1)
        {
            MIN(dp[i+1][j-x[i]],dp[i][j]);
        }
}
cout<<dp[n][x[n]]<<endl;

特殊性质

特殊性质A：就是原题的做法了。

特殊性质B：大概率每走$1000$步就会加油一次，并且要加满，$dp_i$表示走到$i$加满油的最小代价，然后枚举下一次加油的位置，复杂度$O(1000n)$。

正解1

倒着贪心，从$n$到$1$，考虑每一个$i$的决策。

具体一点：

我们假设一共$n$个加油站，第$i$个加油点可以加$p_i$价格的油，接下来要跑$x_i$的距离才能到下一个加油站。

我们考虑从后向前去看每一次决策。

只考虑第$n$个加油站，我显然只需要购买$x_n$的油就足够了。

所以我先记一下：我在$n$号加油站，用$p_n$的价格，购买了$x_n$的油。

在第$n-1$个加油站，首先，如果只有这么两个加油站，我肯定要在$n-1$买$x_{n-1}$的油。这时候，我还可以在这里，用$p_{n-1}$的价格，买最多$C-x_{n-1}$的油。

那么，这里买的油，就可以替代在$n$处购买的油了，对不？

也就是说：如果在此处，$p_{n-1}$比$p_{n}$的决策划算，我就可以用$p_{n-1}$的价格买油，来替代在$p_{n}$买的油。

那么，算法的大框架就出来了：

假设当前我已经考虑了从$i+1$到$n$的所有决策，我当前的决策序列从左到右分别是$[p_{t_1},x_{t_1}],[p_{t_2},x_{t_2}],...$。

那么，当有了$i$以后，我首先需要以$p_i$的价格在$i$购买$x_i$的油。然后，我还有$C-x_i$的油可以在此处买，用来依次替代$t_1,t_2,...,$处的决策。

于是我直接用一个栈来维护这个决策即可，复杂度线性。

核心代码如下：

for (int i=n;i>=1;i--)
{
    //ret:还剩多少可以用，tot:一共加了多少
    ll ret=C-x[i],tot=0;
    //当栈不空，并且栈顶的价格比p[i]大
    while (!S.empty() && ret!=0 && S.top().price>p[i])
    {
        nod tmp=S.top(); S.pop();
        ll num=min(ret,tmp.num); //算一下最多能替代多少
        sum-=num*tmp.price; sum+=num*p[i]; //修改这次决策带来的影响
        tmp.num-=num; tot+=num; ret-=num; 
        if (tmp.num) S.push(tmp);
    }
    sum+=p[i]*x[i];
    S.push(nod(p[i],tot+x[i]));
}

完整代码如下：

#include<bits/stdc++.h>
#define ll long long
#define maxn 1000005
#define mod 1000000007
using namespace std;
ll n,C;
ll x[maxn],p[maxn];
stack<pair<ll,ll>> Q;
int main()
{
	cin>>n>>C;
	for (int i=1;i<=n;i++) cin>>x[i];
	for (int i=1;i<=n;i++) cin>>p[i];
	ll sum=0;
	pair<ll,ll> tt;
	for (int i=n;i>=1;i--)
	{
		sum+=p[i]*x[i];
		ll ret=C-x[i];
		while (ret && !Q.empty())
		{
			tt=Q.top();
			if (tt.first<=p[i]) break;
			Q.pop();
			ll num=min(ret,tt.second);
			sum-=num*(tt.first-p[i]);
			tt.second-=num; ret-=num;
			if (tt.second) Q.push(tt); 
		}
		Q.push({p[i],C-ret});
	}
	cout<<sum<<endl;
}

正解2

上述思路，正着也是可以考虑的。

我们对于第$1$个加油站，认为：我可以在此处，以$p_1$的价格，加$C$的油。

那么，对于第一个加油站来说，我要加$x_1$的油，才能跑到$2$去，所以我此时，还剩下$p_1$价格的$C-x_1$的油。

对于第$2$个加油站，我可以以$p_2$的价格，加$C$的油。

这时候我有这么两个决策：

（1）在加油站$1$，以$p_1$的价格，加$C-x_1$的油。

（2）在加油站$2$，以$p_2$的价格，加$C$的油。

这两个决策显然是矛盾的，因为如果我同时选的话，我怎么可能有$2C-x_1$那么大的油箱呢？

这个时候，我就需要考虑一下了：

假设$p_1<p_2$，那么我就可以认为，我只剩下这么两个决策：

（1）在加油站$1$，以$p_1$的价格，加$C-x_1$的油。

（2）在加油站$2$，以$p_2$的价格，加$x_1$的油。

这样，即便两个加满，也只是$C$。

假设$p_1\geq p_2$，那么我就可以认为，我只剩下这么两个决策：

（1）在加油站$1$，以$p_1$的价格，加$0$的油。

（2）在加油站$2$，以$p_2$的价格，加$C$的油。

可以发现，无论哪种情况发生，我剩下的决策，一定满足下述两个特性：

（1）总加油量是$C$。

（2）从左到右，价格依次递增。

那么我就可以动态的维护这个序列：

到了加油站$i$后，首先把序列末尾，价格比$p[i]$大的那些决策都弹出来。

然后把$p[i]$这个决策，丢到队列的末尾去，保证丢进去的时候，队列内的总油量恰好是$C$。

等维护完这个以后，我就从这个队列里面，贪心的从左到右拿出来$x_i$的油，加到刚刚能去$i+1$即可。

复杂度显然也是线性的。

#include<bits/stdc++.h>
#define ll long long
#define maxn 1000005
#define mod 1000000007
using namespace std;
ll n,C;
ll x[maxn],p[maxn];
pair<ll,ll> Q[maxn+maxn]; 
int head,tail;
int main()
{
	cin>>n>>C;
	for (int i=1;i<=n;i++) cin>>x[i];
	for (int i=1;i<=n;i++) cin>>p[i];
	head=1; tail=1;
	Q[head]={1ll<<30,C}; //为了保证队列里总大小是C
	ll sum=0;
	for (int i=1;i<=n;i++)
	{
		ll tt=0;
        //删掉末尾不如p[i]的决策
		while (head<=tail && Q[tail].first>=p[i]) {tt+=Q[tail].second; tail--;}
		Q[++tail]={p[i],tt};
        //在队列的开头拿出x[i]的油来加
		ll ret=x[i];
		while (ret)
		{
			ll num=min(ret,Q[head].second);
			sum+=Q[head].first*num; Q[head].second-=num; ret-=num;
			if (Q[head].second==0) head++;
		}
		Q[++tail]={1ll<<30,x[i]}; //为了保证队列里总大小是C
	}
	cout<<sum<<endl;
}