Light oj 1018 - Brush (IV) 状态压缩

题目大意:

给出n个点的坐标,求至少画多少掉直线才能连接所有点。

题目思路:状态压缩

首先经行预处理,求出所有状态下,那些点不在该状态内

以任意两点为端点求出这条直线的状态

枚举所有状态,找出不在当前状态下的两点,以这两点所形成的直线经行更新dp。

其中dp[i]表示在i状态下的最优解。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<vector>
#include<algorithm>
#define LL long long
#define MAXSIZE 20
#define INF 0X3f3f3f3f
using namespace std; int dp[],line[MAXSIZE][MAXSIZE];
vector<int>G[]; struct node
{
int x,y;
}point[]; int judge(int a,int b,int c)
{
return (point[a].y - point[c].y)*(point[b].x - point[c].x) == (point[b].y - point[c].y)*(point[a].x - point[c].x);
} int main()
{
for(int i=;i<;i++)
{
G[i].clear();
for(int j=;j<;j++)
{
if((i&(<<j)) == )
G[i].push_back(j);
}
} int T,n,cns=;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=;i<n;i++)
scanf("%d%d",&point[i].x,&point[i].y);
memset(line,,sizeof(line));
memset(dp,INF,sizeof(dp));
for(int i=;i<n;i++)
{
line[i][i]=;
for(int j=i+;j<n;j++)
{
for(int q=;q<n;q++)
{
if(judge(i,j,q))
{
line[i][j] |= (<<q);
}
}
}
}
dp[]=;
for(int i=;i<(<<n);i++)
{
int x=G[i][];
int len=G[i].size();
for(int j=;j<len;j++)
{
int y=G[i][j];
dp[i|line[x][y]] = min(dp[i|line[x][y]],dp[i]+);
}
}
printf("Case %d: %d\n",cns++,dp[(<<n)-]);
}
return ;
}
上一篇:C语言中函数中传入一个数组,并且返回一个数组


下一篇:jQuery解决IE6、7、8不能使用 JSON.stringify 函数的问题