专栏文章

题解：AT_abc288_e [ABC288E] Wish List

TTarganzqq
AT_abc288_e题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mint7kzc
此快照首次捕获于
2025/12/02 07:57
3 个月前
此快照最后确认于
2025/12/02 07:57
3 个月前
查看原文
不难看出来这是个普通的二维 dp，而且性质明显。
我们发现买一件商品时的排名取决于位于它前面且在它和前面买的商品数量，也就是说你先买后面的不会影响前面的。那么我们就设 fi,jf_{i,j} 表示讨论到第 ii 个商品买了 jj 个，此时如果我们要买 ii，就可以在买 jj 个商品时的任意一次买它。因此我们从 k∈[i−j+1,i]k\in[i-j+1,i] 中选一个最小的 ckc_k 作为买它的额外代价。
到这里我一看，涉及到区间查询，难道需要线段树吗？但是再回头一看，n≤5000n\le 5000，预处理就可以。答案就从 fn,i(i∈[m,n])f_{n,i}(i\in[m,n]) 里面选最小的就可以。总时间复杂度 O(n2)O(n^2)。
CPP
#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";
}
/*

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...