题目链接
题目思路
也算是一个比较简单的状压问题不过稍微有点小技巧
设(dp[s])表示消除集合(s)的最小步数
每次枚举集合外的两个点构成一个抛物线,然后再去转移即可
预处理(sta[i][j])表示(i)点和(j)点构成抛物线可以消除哪些小猪
这样复杂度是(2^nn^2)但是可以优化到(2^nn)
因为你加入(i)号点在集合外,那么他迟早要消去,不如现在就把它给直接消去
在第一层for中加个break即可
代码
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=30+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
int n,m;
double x[maxn],y[maxn];
int sta[maxn][maxn];
int dp[1<<18];
int cal(int id1,int id2){
if(abs(x[id1]-x[id2])<eps) return 0;
double a=(x[id2]*y[id1]-x[id1]*y[id2])/(x[id1]*x[id2]*(x[id1]-x[id2]));
if(a>-eps) return 0;
double b=(y[id1]-x[id1]*x[id1]*a)/x[id1];
int sta=0;
for(int i=0;i<n;i++){
if(abs(y[i]-x[i]*x[i]*a-x[i]*b)<eps){
sta|=(1<<i);
}
}
return sta;
}
signed main(){
int _;scanf("%d",&_);
while(_--){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++){
scanf("%lf %lf",&x[i],&y[i]);
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j){
sta[i][j]=(1<<i);
}else{
sta[i][j]=cal(i,j);
}
}
}
for(int i=0;i<=(1<<n)-1;i++){
dp[i]=inf;
}
dp[0]=0;
for(int i=0;i<=(1<<n)-1;i++){
for(int j=0;j<n;j++){
if((i>>j)&1) continue;
for(int k=0;k<n;k++){
if((i>>k)&1) continue;
dp[i|sta[j][k]]=min(dp[i|sta[j][k]],dp[i]+1);
}
break;
}
}
printf("%d
",dp[(1<<n)-1]);
}
return 0;
}
Wow, marvelous weblog layout! How long have you been blogging for?
you make blogging look easy. The total glance of your site
is magnificent, as neatly as the content! You can see similar here e-commerce