P2831 [NOIP2016 提高组] 愤怒的小鸟
思路：考虑先求出经过 \((x_1,y_1),(x_2,y_2)\) 的抛物线解析式
我们有：
\[\begin{cases} ax_1^2 + bx_1 = y_1 \\ ax_2^2 + bx_2 = y_2\end{cases}\]
考虑将 \(b\) 消掉，求出 \(a\)。
那么考虑令 \(1\) 式减去 \(2\) 式的 \(\frac{x_1}{x_2}\) 倍：
\
\
\
因为 \(a\) 太复杂度，不好带入，考虑也将 \(a\) 消掉，求出 \(b\)。
那么考虑令 \(1\) 式减去 \(2\) 式的 \(\frac{x_1^2}{x_2^2}\) 倍：
\
\
\
那么我们可以得到经过 \((x_1,y_1),(x_2,y_2)\) 的抛物线解析式为：
\
可以通过这个解析式求出其它在这个抛物线上的点，设 \(A_{i,j}\) 表示经过点 \(i\) 和点 \(j\) 的抛物线经过的所有点的点集。
考虑状态压缩 dp，令 \(dp_S\) 表示 \(S\) 这个点集的鸟被射下来的最小次数，则：
\
\
\
时间复杂度为 \(O(Tn^22^n)\)。
完整代码：
#include#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);using namespace std;typedef double db;typedef unsigned long long ull;typedef long long ll;bool Begin;const ll N=19,M=(1ll
页:
[1]