【题解】Vitaly and Advanced Useless Algorithms

· · 题解

有一个显然的贪心结论，就是先完成任务截止时间考前的，若在前面的都无法完成，那么后面的更加不可能完成。题目十分良心，a_i 已经在输入时升序给出。

对于每个任务，需要用尽可能少地耗时完成尽可能多的百分比，每个计划的状态均为选或不选，这不就是 0-1 背包嘛。由于要输出方案，所以我们设二维状态，对于某个任务，设 dp_{i,j} 表示该任务的前 i 个计划完成的百分率为 j 时的最小耗时，这里默认 j > 100 时也表示成 j = 100 的状态。所以可以写成方程 dp_{i,j}(j \le [1,100]) = \min (dp_{i - 1,j},\min \{dp_{i - 1,j - p} + t\})，其中有一个是继承上一次的状态。

对于每个任务的方案记录，直接从 dp_{i,100} 进行还原，若 dp_{i,j} ≠ dp_{i - 1,j} 则说明发生有效转移，记录此时的计划编号即可。用一个 vector 去记录会比较遍历，每一次 dp 后将每个人物的方案汇总至总的方案数组即可。

思路不算复杂，不过需要注意 dp，方案记录数组的初始化以及无解的判断。代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#define init(x) memset (x,INF,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 1e5 + 5;
const int MOD = 1e9 + 7;
inline int read ();
struct node
{
    int id,t,p;
};
int t,n,m,ok,sum,a[MAX],dp[MAX][105];
vector <int> ans,v;
vector <node> e[MAX];
int solve (int x);
int main ()
{
    //freopen (".in","r",stdin);
    //freopen (".out","w",stdout);
    t = read ();
    while (t--)
    {
        n = read ();m = read ();ok = 1;sum = 0;ans.clear ();
        for (int i = 1;i <= n;++i) a[i] = read ();
        for (int i = 1;i <= m;++i) 
        {
            int x = read (),ti = read (),pi = read ();
            e[x].push_back ({i,ti,pi});
        }
        for (int i = 1;i <= n;++i)
        {
            int x = solve (i);
            if (x == -1 || sum + x > a[i]){ok = 0;break;}//时间不够
            sum += x;
            for (auto j : v) ans.push_back (j);//答案的汇总
        }
        if (!ok) puts ("-1");
        else
        {
            printf ("%d\n",ans.size ());
            for (auto i : ans) printf ("%d ",i);
            puts ("");
        }
        for (int i = 1;i <= n;++i) e[i].clear ();
    }
    return 0;
}
inline int read ()
{
    int s = 0;int f = 1;
    char ch = getchar ();
    while ((ch < '0' || ch > '9') && ch != EOF)
    {
        if (ch == '-') f = -1;
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar ();
    }
    return s * f;
}
int solve (int x)
{
    int k = e[x].size ();
    for (int i = 0;i <= k;++i)
        for (int j = 0;j <= 100;++j) dp[i][j] = INF;
    v.clear ();
    dp[0][0] = 0;//初始化
    for (int i = 1;i <= k;++i)
    {
        node nw = e[x][i - 1];//注意 vector 的下标存储
        for (int j = 100;~j;--j)
            dp[i][j] = min (dp[i][j],dp[i - 1][max (0,j - nw.p)] + nw.t),dp[i][j] = min (dp[i - 1][j],dp[i][j]);
    }
    if (dp[k][100] == INF) return -1;//无法完成任务
    int p = k,cnt = 100;
    while (p && cnt > 0)
    {
        if (dp[p][cnt] == dp[p - 1][cnt]) {--p;continue;}//说明并没有发生有效转移
        v.push_back (e[x][p - 1].id);//记录编号
        cnt -= e[x][p - 1].p;
        --p;
    }
    return dp[k][100];//最小时间
}