题解 P3921 【小学数学题】
解法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
不给标程啦