CF1941E Rudolf and k Bridges

OPEC · 2024-04-30 14:31:35 · 题解

CF1941E Rudolf and k Bridges

这道题只需要算出每一行最少要花多少，再用前缀和统计即可。

但如果暴力遍历每一个数的话时间复杂度是 O(nm^2) 会超时。

我们需要更省时间的算法。定义 i 为第 i 行，j 为前 j 列，f_j 为到前 j 列。则 f_j=a_{i,j}+\min(f_{i-k-1}\sim f_{i-1})+1，最小值可以用线段树 O(nm\log n) 或单调队列维护 O(nm)。

#include<bits/stdc++.h>
using namespace std;
#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long
const int N=1e2+10,M=2e5+10;
const int INF=0x3f3f3f3f3f3f3f3f;
const int P=998244353;//3221225477
int n,m,k,d,t;
int a[N][M];
int f[M];
struct Node //线段树
{
    int l,r;
    double v;
}tr[4000005];
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mid ((l+r)>>1)
void pushup(int rt)
{
    tr[rt].v=min(tr[lson].v,tr[rson].v);
}
void build(int rt,int l,int r)
{
    tr[rt]={l,r,0};
    if(l==r)
    {
        return;
    }
    build(lson,l,mid);
    build(rson,mid+1,r);
    pushup(rt);
}
void update(int rt,int p,double v)
{
    int l=tr[rt].l;
    int r=tr[rt].r;
    if(l==r)
    {
        tr[rt].v=v;
        return;
    }
    if(p<=mid)
        update(lson,p,v);
    if(p>mid)
    {
        update(rson,p,v);
    }
    pushup(rt);
}
Node query(int rt,int sp,int ep)
{
    int l=tr[rt].l;
    int r=tr[rt].r;
    if(sp<=l&&r<=ep)
    {
        return tr[rt];
    }
    if(ep<=mid)
        return query(lson,sp,ep);
    if(sp>mid)
        return query(rson,sp,ep);
    Node L=query(lson,sp,ep);
    Node R=query(rson,sp,ep);
    Node res;
    res.v=min(L.v,R.v);
    return res; 
}
#undef lson
#undef rson
#undef mid
void solve()
{
    int s[N]={};
    cin>>n>>m>>k>>d;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
//  for(int i=1;i<=n;i++)
//  {
//      build(1,1,m);
//      f[1]=a[i][1]+1;
//      update(1,1,f[1]);
//      for(int j=2;j<=m;j++)
//      {
//          f[j]=a[i][j]+query(1,max((int)1,j-d-1),j-1)+1;//按式子//按式子
//          update(1,j,f[j]);//将这个数放入
//      }
//      s[i]=s[i-1]+f[m];//前缀和统计
//  }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            f[j]=0;
        }
        f[1]=1;
        deque<int> dq;
        dq.push_back(1);
        for(int j=2;j<=m;j++)
        {
            while(!dq.empty()&&dq.front()<j-d-1)
            {
                dq.pop_front();//把不在区间内的删掉
            }
            f[j]=f[dq.front()]+a[i][j]+1;//按式子
            while(!dq.empty()&&f[dq.back()]>=f[j])
            {
                dq.pop_back();//把不在优秀的剔除
            }
            dq.push_back(j);
        }
        s[i]=s[i-1]+f[m];//前缀和统计
    }
    int mn=INF;
    for(int i=k;i<=n;i++)
    {
        mn=min(mn,s[i]-s[i-k]);//求1+i至i+k+1的和中的最小值
    }
    cout<<mn<<'/n';
}
signed main()
{
    fst
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}