【前后缀DP】CF731div3 E

╰+攻爆jí腚メ 2024-03-27 13:54 83阅读 0赞

**这道题想了一会居然被我做出来了，不错，看来我还是有写div3 E的能力的(bushi**

[Problem - E - Codeforces][]

有很多个格子，一些格子里装有空调，每个空调都有一个温度，每个格子最多只能装一个空调，一个格子的权值是：

![53ed43e5e207b816ecbe7ad3c38ea757.png][]

其中a数组表示位置，t数组表示温度

让你求出每个格子的权值

思路：

这道题，并没有一眼DP，一开始以为是个贪心，后来越看越像DP

状态设计：

设dp\[i\]为第i个位置的最小权值

然后去状态转移：

感觉它既可能从前面转移过来，也可以从后面转移过来，所以刚开始想的时候，对于我这种没做过前后缀DP的来说有点困惑，后来试了一下发现真的可以

先做一下前缀DP，表示每个格子从前面的格子能转移过来的最小权值

然后发现需要4种情况分类讨论（其实就两种）

对于0 0（前面没有，后面没有）和1 0（前面有，后面没有）来说：

dp\[i\]=dp\[i-1\]+1

对于另外两种而言：

dp\[i\]=min(dp\[i-1\]+1,t\[i\])

其中如果第一个格子是空的话，dp\[1\]=Mnf，否则就是dp\[1\]=t\[1\]

后缀DP也差不多

Code：

#include <bits/stdc++.h>
    #define int long long
    #define y1 Y1
    const int mxn=3e5+10;
    const int mxe=1e5+10;
    const int mod=1e9+7;
    const int Mnf=1e18;
    const int Inf=-1e18;
    using namespace std;
    struct ty{
        int val,t,pos;
    }p[mxn];
    
    int n,k,x;
    int dp[mxn],dp2[mxn];
    void solve(){
        cin>>n>>k;
        for(int i=1;i<=n;i++){
            p[i].pos=p[i].t=p[i].val=0;
            dp[i]=dp2[i]=0;
        }
        for(int i=1;i<=k;i++){
            cin>>x;
            p[x].val=1;
            p[i].pos=x;
        }
        for(int i=1;i<=k;i++){
            cin>>x;
            p[p[i].pos].t=x;
        }
        int mx_pos=-1;
        for(int i=1;i<=n;i++) mx_pos=max(mx_pos,p[i].pos);
        if(p[1].val==1) dp[1]=p[1].t;
        else dp[1]=Mnf;
        for(int i=2;i<=mx_pos;i++){
            if((p[i].val==0&&p[i-1].val==0)||(p[i-1].val==1&&p[i].val==0)) dp[i]=dp[i-1]+1;
            else dp[i]=min(dp[i-1]+1,p[i].t);
        }
        dp2[mx_pos]=p[mx_pos].t;
        for(int i=mx_pos-1;i>=1;i--){
            if((p[i].val==0&&p[i+1].val==0)||(p[i].val==0&&p[i+1].val==1)) dp2[i]=dp2[i+1]+1;
            else dp2[i]=min(dp2[i+1]+1,p[i].t);
        }
        for(int i=mx_pos+1;i<=n;i++) dp[i]=dp[i-1]+1;
        for(int i=1;i<=mx_pos;i++) cout<<min(dp[i],dp2[i])<<" \n"[i==n];
        for(int i=mx_pos+1;i<=n;i++) cout<<dp[i]<<" \n"[i==n];
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[Problem - E - Codeforces]: https://codeforces.com/contest/1547/problem/E
[53ed43e5e207b816ecbe7ad3c38ea757.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/51b169e0296144e3a0dd927c28e1ff61.png