ggg [ xxx ]表示二进制编码为 xxx 的状态所用的最小步数。 solsolsol [ iii ]表示第 iii 组解。解共有 sss 组。 二进制编码： 状压 DPDPDP 基本概念，二进制数每一位的 111 表示可以达到这个点， 000 表示不能达到这个点。 比如， ggg [ 101010011010100110101001 ]（二进制）表示达到第 111 ， 444 ， 666 ， 888 个点（十进制）所用的最少抛物线数。 解： 能通过仅 111 条抛物线所达到的所有的点组成的二进制编码，叫做一个解。 本题主要分为以下几步： 预处理。此处可用递归。首先枚举两个点，通过两个点共抛物线构造二元一次方程，用公式将其解出。 公式： a1x+b1y=c1a1x+b1y=c1a1x+b1y=c1 , a2x+b2y=c2a2x+b2y=c2a2x+b2y=c2 ,解得 xxx === ( b2b2b2 * c1−b1c1-b1c1−b1 * c2c2c2 )/( a1a1a1 * b2−a2b2-a2b2−a2 * b1b1b1 ), yyy === ( a1a1a1 * c2−a2c2-a2c2−a2 * c1c1c1 )/( a1a1a1 * b2−a2b2-a2b2−a2 * b1b1b1 ). DPDPDP 。此处可以理解为 010101 背包。背包容量为( 1<<n1<<n1<<n ) −1-1−1 ，共 sss 个物品，费用分别为 solsolsol [ 111 ], solsolsol [ 222 ],..., solsolsol [ sss ]，价值均为 111 ，且要求把背包装满，求最小价值。 但是有一个极大的漏洞：比如我们要配出（以下均为二进制） 100110001001100010011000 这个数，一种正确的配法是 10000000+0001100010000000+0001100010000000+00011000 ，但是另 一种拼法是 10000000+00010111+0000000110000000+00010111+0000000110000000+00010111+00000001 ，发生了进位，虽然和依然是 100110001001100010011000 ，但是第 111 个点显然被打了 222 次。 改进方法：另加一重循环，判断是否有重复。时间复杂度 OOO ( nnn ) 本步总时间复杂度： OOO ( smnsmnsmn )，其中 m=1<<nm=1<<nm=1<<n ，可以证明 s<=ns<=ns<=n ^ 222 / 222 ，故复杂度 OOO ( 222 ^ nnn * nnn ^ 333 )，期望得分 757575 ~ 858585 分。 优化 不难发现，比如一条抛物线恰好打中了 111 ， 444 ， 666 ， 888 （均为十进制）这四个点，且不能打中其他的点。则这条抛物 线使 sss 的值增加了 151515 （即( 111 ),( 444 ),( 666 ),( 888 ),( 111 , 444 ),( 111 , 666 ),( 111 , 888 ),( 444 , 666 ),( 444 , 888 ),( 666 , 888 ),( 111 , 444 , 666 ),( 111 , 444 , 888 ),( 111 , 666 , 888 ),( 444 , 666 , 888 ),( 111 , 444 , 666 , 888 ).事实上，由于我们是用最少的抛物线打最多的点，因此最后一种( 111 , 444 , 666 , 888 )的方案比前 141414 种的任意一种都更优。因此，只需在无法继续递归（即没有其他点可以打）时将方案添加到 solsolsol [ sss ]中，很大程度上降低了 sss 的大小。（但 并不能改变最坏复杂度，因为有可能特造一数据使得无任意三点共抛物线） 最重要的优化：我们在背包中进行位运算判断是否重复，因此添加了重复的情况还要舍去，多一维复杂度。不妨逆向思考： ggg [ jjj ] =min=min=min ( ggg [ jjj ], ggg [ j−solj-solj−sol [ iii ] +1+1+1 ),原来可以用要更新的点 jjj 的编号来表示用来更新此点的点 j−solj-solj−sol [ iii ]，现在可以用用来更新此点的点的编号来表示此点。即用 ggg [ jjj ]来更新其他点，而不是用其他点来更新 ggg [ jjj ].这样，我们就可以写出被更新的点的编号： ggg [ iii | solsolsol [ jjj ]]. 注意：二进制原来 1+1=101+1=101+1=10 ，现在 111 | 1=11=11=1 ，不会发生进位，因此无需特判，减小一维复杂度。