题意:
给出n个点, 求过这n个点所需的最少直线条数.
思路:
state表示点的状态,
目的是求出对于某个state, 所需的最小直线条数.
朴素地想state之间的转移情况, 记得要体现"半隐半显"的方法... 那就是枚举一个state中的任意一对点, 去掉这对点所在的直线经过的所有点, 得到state' , 答案就是ans[state] = min(ans[state], ans[state' ] + 1); 枚举所有点对即可. 因为这个state的转移是非线性的, 所以需要用dfs... 现在问题就是如何求出state到state' 的转移. 是否可以想到预处理捏?
预处理出任意两点(i, j)所在直线覆盖的点对应的state(与正文中的state形式相同, 便于使用). 那么就可以暴力地判共线了...居然...这个思路如此理所当然....
拜读的代码:
http://blog.csdn.net/crazy_ac/article/details/7781886
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int inf = ~0u>>2;
int dp[20][20];
int n;
int f[1<<16];
struct point {
int x,y;
}in[20];
int cross(point a,point b,point c){return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);}
bool col(int a,int b,int c){
return cross(in[a],in[b],in[c])==0;
}
void init(){
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
for(int k=0;k<n;k++)//枚举任意两个点和第三个点的id
if(col(i,j,k))//若三点共线
dp[i][j]+=(1<<k);//(上三角矩阵)表示i,j两点连线上有k点
}
int DP(int s)//覆盖s状态的点所需最小直线数
{
if(f[s]!=inf) return f[s];
int cnt=0;
for(int i=0;i<n;i++) if(s&(1<<i)) cnt++;//cnt = __builtin_popcount(s);
if(cnt==0) return f[s]=0;
if(cnt<=2) return f[s]=1;
for(int i=0;i<n;i++)//大于等于三个点时
if(s&(1<<i))//若有一点为i点(正序扫描),只找第一点
{
for(int j=i+1;j<n;j++)//枚举其后的点
if(s&(1<<j))//若找到第二点
{//dp数组居然在下标里用到了!
f[s]=min(f[s],DP(s-(s&dp[i][j]))+1);
}//核心语句就一个,就是用"去掉"操作,来转移到"已知成分更大的状态"
break;//else TLE
}
return f[s];
}//原本我的想法大致相同,只是不会实现...
//这种处理太帅了orz...
int main()
{
int t,ca=1;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d%d",&in[i].x,&in[i].y);
}
init();
fill(f,f+(1<<16),inf);
printf("Case %d: %d\n",ca++,DP((1<<n)-1));//考虑所有点
}
return 0;
}
自己实现一遍:
/*
为何不遍历所有组合而只是选定首个最低位的点,遍历其他的点?
因为这样做(O(n))使得在dfs的每一层,都新选择了一个点;
否则(O(n^2))在不同的层,会多搜索很多重复的情况.
这里有一点贪心的意思,
对于一个点来说,它总是要连掉的,那么每次就考察最低位的点.
这样逐步前进,是不会漏掉什么情况的.
(但整体来说不是很一目了然)
*/
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 20;
const int INF = 0x3f3f3f3f;
int dp[N][N],ans[1<<16],n;
int x[N],y[N];
inline bool col(int i, int j, int k)
{
return !((x[j]-x[i])*(y[k]-y[i])-(x[k]-x[i])*(y[j]-y[i]));
}
void preproc()
{
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
for(int k=0;k<n;k++)
if(col(i,j,k))
dp[i][j] += 1<<k;
}
int dfs(int s)
{
if(ans[s]!=INF) return ans[s];
int cnt = __builtin_popcount(s);
if(!cnt) return ans[s] = 0;
if(cnt<=2) return ans[s] = 1;
int i=0;
while(!((1<<i)&s)) i++;//!
for(int j=i+1;j<n;j++)
{
if((1<<j)&s)
ans[s] = min(ans[s], dfs((s-(s&dp[i][j])))+1);
}
return ans[s];
}
int main()
{
int T,cas = 0;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d%d",x+i,y+i);
preproc();//only use j>i
memset(ans,0x3f,sizeof(ans));
printf("Case %d: %d\n",++cas,dfs((1<<n)-1));
}
}