傳送門

非常有趣的狀壓DP。（對反正我自己又沒想出來）

因為豬的數目非常的少，還是能想到狀壓DP。之后，因為首先小鳥都是從原點發射的，所以我們只需要兩只豬就可以確定一條拋物線。

既然如此，我們就可以枚舉每一對豬，計算出來拋物線的解析式，之后，因為有的時候一條拋物線可以砸死不只一只豬，所以我們可以再枚舉一遍，如果豬在這條拋物線上我們就把這條拋物線能消滅的豬疊加。一條拋物線能消滅的豬使用一個壓縮狀態的二進制數來表示。

在DP的時候，我們考慮所有的情況，對于每種情況去枚舉每一只沒有被消滅的豬，再枚舉另一只豬與之配對。有一些豬只能單獨消滅，那就把他們單獨計算。還有一些豬在被單獨消滅的時候情況可能更優，那我們就多進行一步dp即可。每次在dp的時候更新使用按位或，最后的答案就是dp[(1<<n)-1]。

計算拋物線的式子自己推一下就好。看一下代碼。

#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar('\n')using namespace std; const int M = 1005; const int N = 1000005; const int INF = 1e9; double eps = 1e-7; typedef long long ll;int read() {int ans = 0,op = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-') op = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){ans *= 10;ans += ch - '0';ch = getchar();}return ans * op; }int t,n,m,dp[N],st[25][25]; bool pd[M]; double x[M],y[M]; int calc(int p,int q) {if(x[p] == x[q]) return 0;double a = ((x[q] * y[p] / x[p]) - y[q]) / (x[q] * (x[p] - x[q]));double b = (y[p] - x[p] * x[p] * a) / x[p]; // printf("%.2lf %.2lf\n",a,b);if(a >= 0) return 0;int res = 0;pd[p] = pd[q] = 1;//可以不單獨消滅rep(i,1,n)//尋找其他可以被該小鳥消滅的豬 {double dx = x[i],dy = y[i];if(fabs(a * dx * dx + b * dx - dy) < eps)res |= 1 << (i-1),dp[res] = 1;}return res; }int main() {t = read();while(t--){memset(dp,127/3,sizeof(dp));memset(pd,0,sizeof(pd));memset(st,0,sizeof(st));n = read(),m = read();rep(i,1,n) scanf("%lf%lf",&x[i],&y[i]),dp[1<<(i-1)] = 1;//消滅當前點的小豬需要一只鳥rep(i,1,n)rep(j,1,i-1) st[i][j] = calc(i,j);//計算每條拋物線能打到的豬rep(i,1,(1<<n)-1){rep(j,1,n){if(i & (1<<(j-1))) continue;//這豬已經G了if(!pd[j]) //只能單獨消滅 {dp[i|1<<(j-1)] = min(dp[i|1<<(j-1)],dp[i]+1);continue;}rep(k,1,j-1){if(i & (1<<(k-1))) continue;//這豬G了dp[i|st[j][k]] = min(dp[i|st[j][k]],dp[i] + 1);//更新答案 }dp[i|1<<(j-1)] = min(dp[i|1<<(j-1)],dp[i] + 1);//單獨消滅更好的話在這里更新 }}printf("%d\n",dp[(1<<n)-1]);輸出答案}return 0; } /* 1 2 0 1.00 3.00 3.00 3.00 */

?

轉載于:https://www.cnblogs.com/captain1/p/9607366.html

總結

以上是生活随笔為你收集整理的NOIP2016 愤怒的小鸟的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。