1 条题解

  • 0
    @ 2024-6-12 16:20:05

    暴力部分

    n8n\leq 8

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

    n100,C1000n\leq 100,C\leq 1000

    dpi,jdp_{i,j}表示走到ii,有jj的油的最小代价即可,nC2nC^2复杂度。

    n1000,C10000n\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:大概率每走10001000步就会加油一次,并且要加满,dpidp_i表示走到ii加满油的最小代价,然后枚举下一次加油的位置,复杂度O(1000n)O(1000n)

    正解1

    倒着贪心,从nn11,考虑每一个ii的决策。

    具体一点:

    我们假设一共nn个加油站,第ii个加油点可以加pip_i价格的油,接下来要跑xix_i的距离才能到下一个加油站。

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

    只考虑第nn个加油站,我显然只需要购买xnx_n的油就足够了。

    所以我先记一下:我在nn号加油站,用pnp_n的价格,购买了xnx_n的油。

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

    那么,这里买的油,就可以替代在nn处购买的油了,对不?

    也就是说:如果在此处,pn1p_{n-1}pnp_{n}的决策划算,我就可以用pn1p_{n-1}的价格买油,来替代在pnp_{n}买的油。

    那么,算法的大框架就出来了:

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

    那么,当有了ii以后,我首先需要以pip_i的价格在ii购买xix_i的油。然后,我还有CxiC-x_i的油可以在此处买,用来依次替代t1,t2,...,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

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

    我们对于第11个加油站,认为:我可以在此处,以p1p_1的价格,加CC的油。

    那么,对于第一个加油站来说,我要加x1x_1的油,才能跑到22去,所以我此时,还剩下p1p_1价格的Cx1C-x_1的油。

    对于第22个加油站,我可以以p2p_2的价格,加CC的油。

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

    (1)在加油站11,以p1p_1的价格,加Cx1C-x_1的油。

    (2)在加油站22,以p2p_2的价格,加CC的油。

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

    这个时候,我就需要考虑一下了:

    假设p1<p2p_1<p_2,那么我就可以认为,我只剩下这么两个决策:

    (1)在加油站11,以p1p_1的价格,加Cx1C-x_1的油。

    (2)在加油站22,以p2p_2的价格,加x1x_1的油。

    这样,即便两个加满,也只是CC

    假设p1p2p_1\geq p_2,那么我就可以认为,我只剩下这么两个决策:

    (1)在加油站11,以p1p_1的价格,加00的油。

    (2)在加油站22,以p2p_2的价格,加CC的油。

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

    (1)总加油量是CC

    (2)从左到右,价格依次递增。

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

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

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

    等维护完这个以后,我就从这个队列里面,贪心的从左到右拿出来xix_i的油,加到刚刚能去i+1i+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;
    }
    

    信息

    ID
    1423
    时间
    1000ms
    内存
    512MiB
    难度
    8
    标签
    (无)
    递交数
    130
    已通过
    20
    上传者