【Atcoder】AGC022 C - Remainder Game 搜索

【题目】C - Remainder Game

【题意】给定n个数字的序列A,每次可以选择一个数字k并选择一些数字对k取模,花费2^k的代价。要求最终变成序列B,求最小代价或无解。n<=50,0<=ai,bi<=50。

【题解】首先需要一些性质:

1.一个数字取模k后,再取模>=k的数字就没有意义,因此操作顺序一定是k从大到小,并且每个k只用一次。

2.由于$2^k>2^{k-1}+2^{k-2}+...+2^0$,所以代价最小的序列一定是字典序最小的。

故现在要求字典序最小的严格递减的操作序列k,满足最终变成序列B。(到这里之后,LLQ处理出所有路径然后暴力从大到小推过去了……)

现在从大到小考虑每个k是否必要,如果1~k-1和之前必要的数字形成的集合可以使A变到B,那么k就不是必要的,否则是必要的。

判断是否能到达只需要记f[x]表示x是否能到达,枚举每个数字x,使f[x]=1后从大到小枚举转移。

复杂度O(n^4)。

上一篇:[资源]PHP使用消息队列


下一篇:Linux学习-linux系统下python升级到python3.6步骤详解,以及遇到的问题解决