题解：AT_abc288_e [ABC288E] Wish List

Targanzqq · 2025-09-23 16:04:02 · 题解

不难看出来这是个普通的二维 dp，而且性质明显。

我们发现买一件商品时的排名取决于位于它前面且在它和前面买的商品数量，也就是说你先买后面的不会影响前面的。那么我们就设 f_{i,j} 表示讨论到第 i 个商品买了 j 个，此时如果我们要买 i，就可以在买 j 个商品时的任意一次买它。因此我们从 k\in[i-j+1,i] 中选一个最小的 c_k 作为买它的额外代价。

到这里我一看，涉及到区间查询，难道需要线段树吗？但是再回头一看，n\le 5000，预处理就可以。答案就从 f_{n,i}(i\in[m,n]) 里面选最小的就可以。总时间复杂度 O(n^2)。

#include<bits/stdc++.h>
#define int long long
#define mp make_pair
#define fi first
#define se second
#define lb lower_bound
#define fr front()
#define pii pair<int,int>
#define INF 1e18
using namespace std;

int n,m,a[5005],c[5005][5005],x[5005],f[5005][5005];

signed main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>c[i][i];
    for(int i=1;i<=m;i++)cin>>x[i];
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            c[i][j]=min(c[j][j],c[i][j-1]);
        }
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++)f[i][j]=INF;
    }
    f[0][0]=0;
    for(int i=1,l=1;i<=n;i++){
        for(int j=0;j<=i;j++){
            if(i==x[l]&&j>0)f[i][j]=f[i-1][j-1]+a[i]+c[i-j+1][i];
            else if(i!=x[l]&&j>0)f[i][j]=min(f[i-1][j],f[i-1][j-1]+a[i]+c[i-j+1][i]);
            else if(i!=x[l]&&j==0)f[i][j]=f[i-1][j];
        }
        if(i==x[l])l++;
    }
    int ans=INF;
    for(int i=m;i<=n;i++)ans=min(ans,f[n][i]);
    cout<<ans<<"\n";
}
/*