已添加 hack 数据

第一组数据的输入 hack1.in 为

PLAIN

输出 hack1.ans 为

PLAIN

2
1 3

第二组数据的输入 hack2.in 为 /paste/2bc4k160。

输出 hack2.ans 为

PLAIN

475
1 2 3 4 5 6 7 8 9 11 12 13 14 15 17 19 22 26 27 28 29 30 31 32 34 35 36 37 38 39 41 44 45 46 47 51 53 56 58 59 60 61 63 64 66 68 69 72 73 76 78 79 81 82 83 84 85 86 88 89 90 91 93 94 95 97 99 100

hack 要点：

题目需要输出字典序最小的方案，部分提交未计算出正确的最小字典序。
题解中常见的实现有从 $1$ 到 $n$ 枚举物品进行背包，只有新转移的 DP 值严格大于原先 DP 值时才更新，并同时记录路径。
这种实现的问题在于，在物品价值和相同时，优先选择了最后一个物品编号最小的方案，与题目要求的第一个物品编号最小不完全吻合。查看 hack1.in 与 hack1.ans 可以看出，虽然 $[2]$ 的最后一个物品编号更小，但 $[1, 3]$ 的第一个物品编号更小。
把暴力 DFS 卡出时间限制外了。

参考程序（C++）：/paste/j7bm6nxi。

现存题解广泛存在问题，但经过简单改动可以修复。以 JosephDai 的题解（/blog/_post/183073）为例，将

第 12 行的
for(long long i=1;i<=n;i++) 改为
for(long long i=n;i>=1;i--)；
第 15 行的
if(f[j-a[i]][k-b[i]]+c[i]>f[j][k]) 改为
if(f[j-a[i]][k-b[i]]+c[i]>=f[j][k])；
第 17 行的
ans[j][k]=ans[j-a[i]][k-b[i]]+char(i); 改为
ans[j][k]=char(i)+ans[j-a[i]][k-b[i]];；

即可通过新数据，见 R108070349。

反馈者 tokitsukaze 的提交 R108008354 也不能通过新数据，但只需要将第 30 到 50 行删除并改为

CPP

ans=dp[1][m][v];
x=1;
y=m;
z=v;

即可通过新数据，见 R108070355。

今日晚些时候会撤下不能通过新数据的题解并开放题解通道，在此期间用户可以测试现有题解是否可以通过新数据（请确保已经自行通过本题）。

讨论操作

回复

相关推荐

已添加 hack 数据