自动搬运

查看原文

来自洛谷，原作者为

	zxdjmq 蒟蒻，还是因为自己不够努力 | 舟 B服 栖金杨之忠雀#9399

搬运于2025-08-24 23:10:32，当前版本为作者最后更新于2025-03-30 13:47:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P11827 [TOIP2024] 大步小步向前走

解法说明

题面看起来就像 DP，所以想一想 DP 怎么做。

转移方程是显然的，枚举每一个可走的点向前找有哪些点可以转移过来，找一下最优解。

注意到数据范围 $k \times (e-n)\leq 3\times 10^5$，这意味着我们可以用 vector 存储当前步法数量。同时 vector 又非常好的特性：我们可以用内置的比较运算符比较两个 vector 的字典序，完美适配该题的比较方式。

由于题目还要求我们输出方案，那么把每个点的转移来源存下来即可。

时间复杂度 $O(k^2(e-n)^2)$，但是由于比较字典序的 $O(k(e-n))$ 根本跑不满，所以跑得飞快。

代码

#include<bits/stdc++.h>
using namespace std;
// #define int long long
// #define il inline
#define pb push_back
const int N=3e5+10,inf=1e9;

int n,m,k,a[N];
bool ok[N];
vector<int> dp[N];
int fr[N],cnt[N];

bool cmp(int x,int y){return x>y;}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin>>m>>k>>n;
    for(int i=0;i<=n;i++)ok[i]=1,fr[i]=inf;
    for(int i=1;i<=m;i++){
        int qw;
        cin>>qw;
        ok[qw]=0;
    }
    for(int i=1;i<=k;i++){
        cin>>a[i];
    }

    sort(a+1,a+k+1,cmp);
    dp[0].resize(k+10);

    for(int i=1;i<=n;i++){
        if(!ok[i])continue;
        dp[i].resize(k+10);
        dp[i][1]=-1;
        cnt[i]=inf;
        for(int j=k;j>=1;j--){
            if(i-a[j]<0)break;
            if(!ok[i-a[j]])continue;
            dp[i-a[j]][j]++;
            if(cnt[i-a[j]]!=inf && dp[i-a[j]]>dp[i]){
                dp[i]=dp[i-a[j]];
                cnt[i]=cnt[i-a[j]]+1;
                fr[i]=i-a[j];
            }
            dp[i-a[j]][j]--;
        }
    }
    if(cnt[n]==inf){
        cout<<-1;
        return 0;
    }
    cout<<cnt[n]<<'\n';
    int ans[N],nw=n,pos=0;
    while(nw>0){
        ans[++pos]=nw;
        nw=fr[nw];
    }
    for(int i=cnt[n];i>=1;i--)cout<<ans[i]<<' ';
    return 0;
}