自动搬运

查看原文

来自洛谷，原作者为

	oscar **

搬运于2025-08-24 21:54:06，当前版本为作者最后更新于2017-09-09 12:57:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解法0：

学习⑨，输出-1 0

期望得分：0分

解法0.5：

输出1 1

期望得分：10分

解法1：

将所有人的位置作为状态，建出图来暴力BFS+DP

加入状态压缩优化常数

条件1等价于状态i中i&((1<<(a-1))|(1<<(b-1)))0或i&((1<<(a-1))|(1<<(b-1)))((1<<(a-1))|(1<<(b-1))) 条件2可以进行类似的转化

不要忘记考虑条件2中b==c的情况

时间复杂度O(2^(2*n))

期望得分:30~70分（取决于常数）

解法2：

优化建图

新建节点(i,j,k)表示与状态i 后j位完全相同 且 剩余位置上差异恰有k位

从(i,j,k)向(i,j-1,k)和(i^(1<<(j-1)),j-1,k+1)连一条权值为0的边

再从(i,0,k)向(i,n,0)连一条权值为1的边（0<=k<=r）

最后从((1<<n)-1,0,k)向T连一条权值为0的边(0<=k<=r)

再在新图上跑BFS+DP

时间复杂度O((n^2)*(2^n))

期望得分90~100分（取决于常数）

有一点细节，DP的时候需要当做所有边权值为1跑，否则答案会出问题（更新顺序不对）

呜呜呜~~~比赛时被解法1水过了（90分），很不开心QAQ

不给标程啦