题解：AT_abc288_e [ABC288E] Wish List

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}

。

CPP

#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;
}

题解：AT_abc288_e [ABC288E] Wish List

文章操作

相关推荐

评论

题解：AT_abc288_e [ABC288E] Wish List