NOIP 2016憤怒的小鳥(狀壓DP)

60分做法:

暴力枚舉兩個沒被覆蓋點,形成一個合法的拋物線,在掃一遍能在拋物線上的點,打上標記即可。

#include<queue>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
int t;
int n,m,U,w;
double x[30],y[30];
int p[30];
int ans=0;
bool vis[30];
bool check(int id,double a,double b)
{
 if(fabs(a*x[id]*x[id]+b*x[id]-y[id])<=0.000001)
 return 1;
 return 0;	
}
void dfs(int cnt,int sum)
{
  if(sum>ans||w>U) return;
  if(cnt==n)
  {
   ans=min(ans,sum);
   return;	
  }
  for(int i=1;i<=n;i++)
  {
   if(vis[i]) continue;
   for(int j=i+1;j<=n;j++)
   {
   	 w++;
     if(vis[j]) continue;
     double a=(x[j]*y[i]-x[i]*y[j])/(x[i]*x[j]*(x[i]-x[j]));
     double b=(y[i]-a*x[i]*x[i])/x[i];
     if(a>=0) continue;
     vis[i]=vis[j]=1;
     int tot=0;
	 for(int k=j+1;k<=n;k++)//因為在前面能選的點,之前也可以枚舉到,這種情況可以覆蓋到現在這個情況,所以可以從j往后枚舉,減少重復情況
	 {
	   if(vis[k]) continue;
	   if(check(k,a,b))
	   vis[k]=1,p[++tot]=k;
	 }
	 dfs(cnt+2+tot,sum+1);
	 for(int k=1;k<=tot;k++)
	 vis[p[k]]=0;
	 vis[i]=vis[j]=0;
   }
  }
  ans=min(n-cnt+sum,ans);
}
int main()
{
 scanf("%d",&t); U=20000000/t;//卡時能過75
 while(t--)
 {
  w=0;
  ans=1e9;
  memset(vis,0,sizeof(vis));
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++)
  scanf("%lf%lf",&x[i],&y[i]);
  dfs(0,0);
  printf("%d\n",ans);
 }
 return 0;	
}

滿分做法:

看到n<=18,可以想到狀壓DP。\(dp[S]\)表示表示已經死了的豬的集合狀態為S時最少要發射的鳥數(即拋物線)。

考慮轉移:

\(dp[0]=0\)

\(dp[S|line[i][j]]=\min(dp[S|line[i][j]],dp[S]+1)\)

\(dp[S|(1<<(i-1)]=\min(dp[S|(1<<(i-1)],dp[S]+1)\)(單獨打一個豬)

\(line[i][j]\)表示第i個點和第j個點連成的拋物線可以打死豬的集合。

本題可以優化到\(O(Tn2^n)\).令\(low[S]\)表示S狀態第一個零的位置。這個位置是一定要打的,如果這一次轉移不打,那以后還要再回過頭來打,這就是多余的轉移。所以由 S擴展的轉移的所有線都要經過\(low[S]\)。之后枚舉拋物線即可。

#include<queue>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
const int maxm=1<<20;
const double eq=1e-8;
int t;
int n,m;
double x[30],y[30];
int low[maxm];//表示i狀態的第一個0的位置 
int dp[maxm];//表示i狀態的最少拋物線數 
int line[30][30];//表示經過i,j的拋物細經過所有點的狀態 
bool check(int id,double a,double b)
{
 if(fabs(a*x[id]*x[id]+b*x[id]-y[id])<=eq)
 return 1;
 return 0;	
}
int main()
{
 for(int i=0;i<(1<<18);i++)
 {
   int j=1;
   for(;j<=18,i&(1<<(j-1));j++);
   low[i]=j;
 }
 scanf("%d",&t);
 while(t--)
 {
  memset(dp,63,sizeof(dp));
  memset(line,0,sizeof(line));
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++)
  scanf("%lf%lf",&x[i],&y[i]);
  for(int i=1;i<=n;i++)
  {
  	for(int j=1;j<=n;j++)
  	{
  	  if(fabs(x[i]-x[j])<eq) continue;
  	  double a=(x[j]*y[i]-x[i]*y[j])/(x[i]*x[j]*(x[i]-x[j]));
      double b=(y[i]-a*x[i]*x[i])/x[i];
      if(a>-eq) continue;
      for(int k=1;k<=n;k++)
      {
       if(check(k,a,b))
	   line[i][j]|=(1<<(k-1));	
      }
  	}
  }
  dp[0]=0;
  for(int i=0;i<(1<<n);i++)
  {
    int j=low[i];//能過的點盡量早過 
    dp[i|(1<<(j-1))]=min(dp[i|(1<<(j-1))],dp[i]+1);
    for(int k=1;k<=n;k++)
	dp[i|line[j][k]]=min(dp[i|line[j][k]],dp[i]+1);
  }
  printf("%d\n",dp[(1<<n)-1]);
 }
 return 0;	
}
posted @ 2019-10-12 10:06  lihan123  閱讀(20)  評論(0編輯  收藏
七乐彩2011年走势图南方双彩