题解：CF1650F 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$，方案记录数组的初始化以及无解的判断。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
| #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 ()
{
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];
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];
}
|
