题解：AT_abc288_e [ABC288E] Wish List

Lucyna_Kushinada · 2025-02-04 17:32:45 · 题解

dp 好题，难点在于看清 “编号第 j 小” 的本质，以及对于方程的设计。

令 dp_{i,j} 为前 i 个中买了 j 个，且必买的全买了的最小价值。

于是我们可以套路地是可以从选和不选来转移，但需要注意必买的只能选，不可以不选，其他的则没什么关系。

不选显然可以通过 dp_{i,j}=\min (dp_{i-1,j}) 转移，下面来讨论选的情况的转移。

在这 j 次购买中，我们既可以决定第 1 次就把 i 买了，也可以第 j 次才买 i。如果是第 1 次就把 i 买了，总价就是 (c_i+a_i)，如果第 j 次才买 i，那么总价就是 (c_{i-j+1}+a_i)，因为我们要求最小的，所以贡献就是 (\min_{k=i-j+1}^{i}c_k+a_i)，故选第 i 个的转移方程就是 dp_{i,j}=dp_{i-1,j-1}+\min_{k=i-j+1}^{i}c_k+a_i。

那么答案就是 \min_{i=m}^n dp_{n,i}。

#include<bits/stdc++.h>
using namespace std;

#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(r);i>=(l);--i)
#define pr pair<int,int>
#define fi first
#define se second
#define pb push_back

#define N 5055
#define M 13
#define int long long

int n,m,a[N],c[N],x,mn[N][N],dp[N][N];
bitset<N>f;

signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n>>m;
    rep(i,1,n){
        cin>>a[i];
    }
    rep(i,1,n){
        cin>>c[i];
    }

    int x;
    rep(i,1,m){
        cin>>x;
        f[x]=1;
    }

    rep(i,1,n){
        mn[i][i]=c[i];
        rep(j,i+1,n){
            mn[i][j]=min(mn[i][j-1],c[j]);
        }
    }

    rep(i,0,n){
        rep(j,0,n){
            dp[i][j]=1e15;
        }
    }
    dp[0][0]=0;

    rep(i,1,n){
        rep(j,1,i){
            dp[i][j]=min(dp[i][j],dp[i-1][j-1]+mn[i-j+1][i]+a[i]);
        }

        if(f[i])continue;

        rep(j,0,i){
            dp[i][j]=min(dp[i][j],dp[i-1][j]);
        }
    }

    int ans=1e15;

    rep(j,m,n){
        ans=min(ans,dp[n][j]);
    }

    cout<<ans;

    return 0;
}