题解：CF1650F Vitaly and Advanced Useless Algorithms

· · 题解

题意

每个任务有一个 DDL，和若干个行动，可以花费一定时间完成该任务的百分之几。求能够在每个任务的 DDL 之前完成任务的行动方案。

解法

贪心地想，当达到一个任务的 DDL 时，我们必须学完在这之前可以保证这个任务被学完的最少时间。出题人比较良心，直接将 DDL 升序，把时间作为价值，这一时间就可以在遍历到每个 DDL 的时候通过 01 背包处理出。

但是，这道题还要求记录路径，怎么办呢？

一个通用的办法是在二维 dp 数组上额外记录一个数据，说明“这个状态由哪个状态转移而来”，但是我比较头铁，坚持使用滚动数组。众所周知，路径是一条链，因此我们可以使用链式前向星，每一次转移把对应的头指针连到上一个转移而来的头指针上。于是乎，记录路径就如此搞定了。

AC Code

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

const int inf=0x3f3f3f3f3f3f3f3f;

void solve(){
    int n,m,cur_t=0;
    cin>>n>>m;
    vector<int> ans;
    vector<int> a(n+1);
    vector<tuple<int,int,int>> task[n+1]; //id,t,p
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1,e,t,p;i<=m;i++){
        cin>>e>>t>>p;
        task[e].push_back(make_tuple(i,t,p));
    }
    for(int i=1;i<=n;i++){
        vector<pair<int,int>> rec(1); //id, nxt
        pair<int,int> dp[101]; //存放价值和头指针
        for(int j=1;j<=100;j++) dp[j].first=inf;
        for(auto& at:task[i]){
            int id,t,p;
            tie(id,t,p)=at;
            for(int j=100;j>=0;j--){ //fr
                if(dp[min(100,j+p)].first<=dp[j].first+t) continue; 
                rec.push_back({id,dp[j].second});
                dp[min(100,j+p)]={dp[j].first+t,rec.size()-1}; //将>100的状态压缩为100
            }
        }
        cur_t+=dp[100].first; //背包总价值
        if(cur_t>a[i]){ //若当前时间>ddl则无解
            cout<<"-1\n";
            return;
        }
        stack<int> st; //使用栈是为了倒序输出
        for(int u=dp[100].second;u;u=rec[u].second) st.push(rec[u].first);
        for(;st.size();st.pop()) ans.push_back(st.top());
    }
    cout<<ans.size()<<'\n';
    for(auto& at:ans) cout<<at<<' ';
    cout<<'\n';
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}

复杂度分析

时空均为 O(nm) 。