Brush (IV) LightOJ

题意：平面上有一些点，每刷一次可以把同一条直线上的点都刷光，问最少几次把所有点刷光。

方法：

显然是一个状态压缩dp。ans[S]表示把S集合中点刷掉的最少次数。最开始想到的方法是如果S中只有一个或两个点，那么ans[S]=1。否则枚举S中任意两点i,j作为直线上的点，并算出经过i,j的直线还过S中其他多少个点，那么ans[S]=min(ans[S],ans[S去掉那条直线经过的所有点]+1)。自然而然的就想到应该预处理出过i,j两点的直线过的其他点的集合，只需要枚举i,j和另外一个点再判是否共线即可。

这里需要用到判三点共线：https://www.zybang.com/question/ca7778a2e315afb588629121177b6772.html

A(x1,y1),B(x2,y2),C(x3,y3),则(x2-x1)×(y3-y2)=(x3-x2)×(y2-y1)

但是，这样时间复杂度是$O(T*n^3*2^n)$，还是太慢了。

观察一下可以发现：由于一个集合中所有点早晚都要刷掉，只需要指定任意一个点作为直线上的点，再枚举另一个点就行了。

那么，复杂度降低到$O(T*n^2*2^n)$。对于单组数据复杂度已经可以接受，但是由于T比较大，还是不能通过。

接下来开始卡常：

1.把循环的dp改成记忆化搜索能快许多，因为最终状态不一定需要其他所有状态的答案。

2.在开始时预处理出每个集合S的所有元素，而不是每次枚举编号判断是否在S内

3.常规（meiyong）：快读，预处理左移

错误记录：

1.复杂度错误，$O(T*n^3*2^n)$

2.被卡常，用http://blog.csdn.net/kijamesqi/article/details/50533691的方法卡过去

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int x[],y[];

 int T,TT,n,fff;

 int ans[];

 int tmp[][];

 int left[];

 int G[][];

 void read(int&x)

 {

     x=;

     char ch=getchar();fff=;

     while(ch<''||ch>'')

     {

         if(ch=='-')    fff=-;

         ch=getchar();

     }

     while(ch>=''&&ch<='')    x=(x<<)+(x<<)+ch-'',ch=getchar();

     x*=fff;

 }

 int main()

 {

     int i,j,k,t1,t2;

     for(i=;i<;i++)    left[i]=(<<i);

     for(i=;i<;i++)

         for(k=;k<;k++)

             if(i&left[k])

                 G[i][++G[i][]]=k;

     read(T);

     for(TT=;TT<=T;TT++)

     {

         read(n);

         for(i=;i<n;i++)

             read(x[i]),read(y[i]);

         //memset(tmp,0,sizeof(tmp));

         for(i=;i<n;i++)

             for(j=i+;j<n;j++)

             {

                 tmp[i][j]=;

                 t1=x[j]-x[i];

                 t2=y[j]-y[i];

                 for(k=;k<n;k++)

                     if(t1*(y[k]-y[j])==(x[k]-x[j])*t2)

                         tmp[i][j]|=left[k];

                 tmp[j][i]=tmp[i][j];

             }

         //memset(ans,0x3f,sizeof(ans));

         ans[]=;

         for(i=;i<left[n];i++)

         {

             if(__builtin_popcount(i)<=)

                 ans[i]=;

             else

             {

                 ans[i]=0x3f3f3f3f;

                 //每个点都迟早要被刷，因此枚举任意一个点作为直线上点即可，不用枚举两个

                 j=G[i][];

                 for(k=;k<=G[i][];k++)

                     ans[i]=min(ans[i],ans[i^(tmp[j][G[i][k]]&i)]+);

             }

         }

         printf("Case %d: %d\n",TT,ans[left[n]-]);

     }

     return ;

 }

巴特西

Brush (IV) LightOJ - 1018

最新文章

热门文章