复赛在即，我们学校里面的四个撒币不知道是谁突发奇想，说要出一套模拟题。于是我们四个人分别出了一道要多恶心有多恶心的题= =本来嘛是要在学校内部自己测的，不过人太少，不好玩，于是就连夜 py 到洛谷上搞了公开赛。从早上 8 点到中午 12 点，虽然出了很多的锅，不过还是要记录一下我的第一次出题经历（
感受
各位有兴趣看题目的话地址在这里： https://www.luogu.org/contest/show?tid=4291 https://www.luogu.org/problemnew/show/U14667
安排给我的出题难度是压轴（也就是最难的那一题），不过被我活生生出成了水题= =……出了一道状压 DP 的模板题（大概），然后呢并没有人帮我验题（事实上他们三个人互相 A 不掉对方的题目总共前前后后调到比赛都开始了还在出锅）……
于是因此发生了一件很尴尬的事情，就是造数据的时候呢，因为 std 出了锅少写了一个等于号，然后造出了一堆错误的数据，把正解卡到了 30 分= =比赛完了之后写题解才发现，卧槽标程都出锅了，然后更新数据、重传数据，联系了 luogu 的管理员帮我们重测，然后还一个一个给可能写了正解的参赛者发私信道歉+让他们请求重新提交……
提交了 80 多个人有将近 90% 是输出 No Answer 骗分的233333早知道不设这个点了（
最后重新提交完有两个写出了正解的 julao，一个写了接近正解但是差一点的 dalao……嘛，看起来这题出得还是挺水的（不过话说回来，比同校人出的那些题良心多了2333
接下来是题目：
肝活动 (event.pas/.c/.cpp)
时间限制：1s / 空间限制：512MB / 测试点数目：20
题目描述
Yume 最近在玩一个名为《LoveLive! School idol festival》的音乐游戏。他之所以喜欢上这个游戏，是因为这个游戏对非洲人十分友好，即便你脸黑到抽不出好卡，还可以通过在每个月举办的两次活动中达成一定的目标来获得奖励。 Yume 很喜欢这一期活动奖励卡的卡面，于是他决定要肝这一期的活动，拿到活动奖励。这一期的活动规则很特殊，玩家需要在活动规定的结束时间前，完成所有指定的歌曲（每首歌只能打一次），并获得一定的分数，就可以拿到活动奖励。如果在规定的时间前没有完成所有的歌曲，或者分数不够奖励的分数线，则不能领取活动奖励。每首歌有一个限定的奖励开放时间，玩家如果在这段时间内完成了这首歌，便可以获得一定的分数（获得的分数 = 开放时间 - 当前已用的总时间）。如果超出了这段时间之后再完成这首歌，就不能获得分数了。 这样的规则对 Yume 这样的老玩家来说本应是轻而易举，但不巧的是 Yume 把活动的结束时间记成了活动的开始时间，以至于当他上线跃跃欲试的时候，惊恐地发现活动已经快要结束了。现在他想知道，在剩余的时间之内，他能否完成所有的歌、达成奖励的分数线拿到活动卡。为了节省时间，他把这个问题交给了你来解决。请你根据给定的数据，帮他计算出能否在剩余的时间内达成目标。如果能，请告诉他完成每首歌曲的顺序。
输入数据
从文件 event.in 读取输入数据。 输入的第一行是三个整数 n, m, t，分别表示规定完成的歌曲数目、获得奖励需要达到的最低分数和距离活动结束剩余的时间。 接下来有 n 行，第 i 行有一个字符串 Si 和两个整数 Ti 和 Mi，表示第 i 首歌的歌名为 Si，完成第 i 首歌所需要的时间为 Ti，第 i 首歌的奖励开放时间剩余 Mi。保证 Ti ≤ Mi. 其中数据已按 Si 的字典序给出。
输出数据
将答案输出到 event.out 中。 如果在活动结束前 Yume 可以完成指定的目标拿到奖励，则在第一行输出一个整数 C，表示在获得奖励的前提下，所能够获得的分数的最大值；接下来的 n 行中，按照完成歌曲的顺序输出第 i 首歌的歌名。如果有多种可能性，则输出字典序最小的情况。 如果在活动结束前 Yume 不能完成所有的歌曲，输出 No Answer .
输入样例
【样例1】 3 2 10 BokutachiwaHitotsunoHikari 3 8 Korekara 1 2 SnowHalation 2 5
【样例2】 2 1 2 AoizoraJumpingHeart 1 2 TimeLapse 2 4
输出样例
【样例1】 6 SnowHalation BokutachiwaHitotsunoHikari Korekara
【样例2】 No Answer
样例1说明： 首先打第三首歌，用时 2，获得分数为 (5-2)=3； 接着打第一首歌，用时 3，获得分数为 (8-2-3)=3； 最后打第二首歌，用时 1，由于打完第二首歌之后总用时为 6，但第二首歌的奖励获得时间为 2，因此不能获得分数。 总用时为 6 < 10，分数为 6 > 2，完成目标。
数据规模
对于 0% 的数据，与测试数据完全相同。 对于 20% 的数据，满足 n ≤ 5。 对于 40% 的数据，满足 n ≤ 9。 对于 70% 的数据，满足 n ≤ 15。 对于 100% 的数据，满足 n ≤ 22，Si 的长度不超过 50. 保证 m, t 和 Ti, Mi 以及其相加的结果都在 int 的最大范围内。 另有 10% 的数据满足 Sigma(T1, T2, …, Tn) < t.
题解
没错，这是一道状态压缩 DP（而且事实上是道水题吧，感觉对不起提高+/省选-的评级 Orz）。很多人没写出来大概是因为被这个比赛发起人瞎 YY 的评级吓到了……不太明白状态压缩 DP 原理的= =嘛，建议先去理解一下，出题人太懒，不想在题解里写状压 DP 的原理（逃
首先要读懂题目的意思，找出关键的信息，这个不多说。注意一下分数的计算方式和获得奖励的条件即可。
先考虑无解的情况，第一种情况是当 Sigma(T1, T2, T3, ..., Tn) < t 的时候，在剩余时间内无法完成所有的歌，很明显应该输出 No Answer.
还有一种情况是即便在规定时间内打完了所有的歌，仍然达不到规定的分数 m 的时候，也是 No Answer，这种情况我们只能找到最大值后才计算。可惜有一位离正解很近的 julao 忘记了这种情况被砍掉了 15 = =
再就是状态的设计。题目中规定要完成每首歌，并且每首歌都只能打一次，那么我们设 dp[i] 表示当前已完成的歌曲编号的二进制状态为 i 的情况下，能取得的分数的最大值。
那么转移方程就显然了：dp[i] = max(dp[i], dp[i & (~j)] + limit[j] - curTime[i])，其中 j 是当前考虑的歌曲编号，那么 i & (~j) 就是打第 j 首歌之前的状态，limit[j] 表示能获得奖励分数的规定时间，curTime[i] 就是打完第 j 首歌之后的总用时。
我们可以看到完成的歌曲的二进制状态为 i 时所用的时间 curTime[i] 与打歌的顺序无关，所以我们可以预处理计算出这个 curTime 数组:
for (int i = 0; i < (1 << 22); i++)
{
for (int j = 0; j < n; j++)
{
// 状态 i 已经包含了第 j 首歌
if (i & j) {
continue;
}
curTime[i | j] = curTime[i] + cost[j];
}
}
当然你也可以不做这一步，直接在 DP 的时候更新当前状态的时间也没有问题。
接下来我们就可以写出 DP 的主过程了。Wait, 在此之前，细心的各位想必已经注意到了题目中的一个需求，如果多种打歌顺序都可获得最大值的话，那么要输出字典序最小的方案。这个怎么解决呢？再细心看一下题目会发现每首歌在给出的时候已经强调按照字典序排好了，所以我们只需要把正序枚举 j from 1 to n 改成逆序枚举 j from n to 1，这样就可以保证在遇到字典序更小的最优解的时候替换掉当前解。
for (int i = 0; i <= (1 << n); i++)
{
for (int j = n; j >= 0; j--)
{
int cur = 1 << j;
if (i & cur) {
int prev = i & (~cur);
int getscore = rest[j] - curTime[prev] - cost[j];
if (getscore < 0) {
getscore = 0; // 记得把不能得到分数的情况修改掉
}
// 注意这里的条件是 <=，因为当得分相等的时候取字典序更小的更优
if (dp[i].score <= dp[prev].score + getscore) {
dp[i].score = dp[prev].score + getscore;
dp[i].cur = j;
dp[i].prev = prev;
}
}
}
}
最后我们顺着 dp[(1 << n) - 1] 的状态一路推回去输出方案。在此之前别忘了再判断一下 m 与 dp[(1 << n) - 1] 的大小关系。还有一个要注意的地方是输出顺序的问题，因为是从最后一个推回去的，但是应该从第一个输出到最后一个，所以这个时候做一个 DFS 或者丢进栈里就完美啦。
附上蒟蒻的标程
#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;
const int MAXS = (1 << 24);
const int MAXN = 25;
struct State {
int cur;
int prev;
int score;
};
State dp[MAXS + 20];
int n, m, t;
int sum;
int cost[MAXN], rest[MAXN];
int curTime[MAXS + 20];
char name[MAXN][110];
int main()
{
memset(curTime, 0, sizeof curTime);
memset(dp, 0, sizeof dp);
scanf("%d%d%d", &n, &m, &t);
for (int i = 0; i < n; i++)
{
scanf("%s%d%d", name[i], &cost[i], &rest[i]);
sum += cost[i];
}
if (t < sum) {
printf("No Answer");
return 0;
}
for (int i = 0; i < (1 << n); i++)
{
for (int j = n; j >= 0; j--)
{
if (i & (1 << j)) {
continue;
}
int next = i | (1 << j);
curTime[next] = curTime[i] + cost[j];
}
}
for (int i = 0; i <= (1 << n); i++)
{
for (int j = n; j >= 0; j--)
{
int cur = 1 << j;
if (i & cur) {
int prev = i & (~cur);
int getscore = rest[j] - curTime[prev] - cost[j];
if (getscore < 0) {
getscore = 0;
}
if (dp[i].score <= dp[prev].score + getscore) {
dp[i].score = dp[prev].score + getscore;
dp[i].cur = j;
dp[i].prev = prev;
}
}
}
}
int state = (1 << n) - 1;
if (dp[state].score >= m) {
printf("%d\n", dp[state].score);
} else {
printf("No Answer");
return 0;
}
stack<int> S;
while (state != 0)
{
S.push(dp[state].cur);
state = dp[state].prev;
}
while (!S.empty())
{
int id = S.top();
S.pop();
printf("%s", name[id]);
if (!S.empty()) {
printf("\n");
}
}
return 0;
}