題目
題解
由于n<=18，可以想到狀壓dp
然後選擇枚舉一個抛物線，直接更新
如果用填表法，就會有些難度，而時間複雜度是O（
）
且
其中cnt表示i的點集減去抛物線的點集
代碼
//可是用了O2才過
#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int MAXN = 20;
int n , m , T;
int dp[1<<MAXN];
int sum[MAXN*MAXN][MAXN] , cnt;
double a[MAXN] , b[MAXN];
int main()
{
scanf( "%d" , &T );
while( T -- ){
cnt = 0;
scanf( "%d%d" , &n , &m );
memset( sum , 0 , sizeof( sum ) );
memset( dp , 0x7f, sizeof( dp ) );
for( int i = 1 ; i <= n ; i ++ ){
scanf( "%lf%lf" , &a[i] , &b[i] );
sum[++cnt][1] = i;sum[cnt][0] = 1;
}
for( int i = 1 ; i <= n ; i++ ){
for( int j = i + 1 ; j <= n ; j ++ ){
if( a[i] * a[i] * a[j] - a[j] * a[j] * a[i] == 0 ) continue;
double ans1 = ( a[j] * b[i] - a[i] * b[j] ) / ( a[i] * a[i] * a[j] - a[j] * a[j] * a[i] );
if( ans1 < 0 ){
cnt ++;
sum[cnt][0] = 2;
sum[cnt][1] = i , sum[cnt][2] = j;
for( int k = 1 ; k <= n ; k ++ ){
if( k == i || k == j ) continue;
if( a[j] * a[j] * a[k] - a[k] * a[k] * a[j] == 0 ) continue;
double ans2 = ( a[k] * b[j] - a[j] * b[k] ) / ( a[j] * a[j] * a[k] - a[k] * a[k] * a[j] );
double t = ans1;
if( t < ans2 ) swap( t , ans2 );
if( t - ans2 < 1e-6 )
sum[cnt][++sum[cnt][0]] = k;
}
}
}
}
dp[0] = 0;
for( int i = 1 ; i < ( 1 << n ) ; i ++ ){
for( int j = 1 ; j <= cnt ; j ++ ){
int p = i;
for( int k = 1 ; k <= sum[j][0] ; k ++ ){
int x = sum[j][k];
if( p & ( 1 << ( x -1 ) ) )
p = p ^ ( 1 << ( x -1 ) ) ;
}
dp[i] = min( dp[p] + 1 , dp[i] );
}
}
printf( "%d\n" , dp[( 1<<n)-1] );
}
return 0;
}
這樣的效率太慢了，如果用刷表發就可以
時間複雜度
其中cnt表示的是枚舉的是抛物線經過的點集
代碼
#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int MAXN = 20;
int n , m , T;
int dp[1<<MAXN];
int sum[MAXN*MAXN], cnt;
double a[MAXN] , b[MAXN];
int main()
{
scanf( "%d" , &T );
while( T -- ){
cnt = 0;
scanf( "%d%d" , &n , &m );
memset( sum , 0 , sizeof( sum ) );
memset( dp , 0x7f, sizeof( dp ) );
for( int i = 1 ; i <= n ; i ++ ){
scanf( "%lf%lf" , &a[i] , &b[i] );
sum[++cnt] = 1 << (i-1);
}
for( int i = 1 ; i <= n ; i++ ){
for( int j = i + 1 ; j <= n ; j ++ ){
if( a[i] * a[i] * a[j] - a[j] * a[j] * a[i] == 0 ) continue;
double ans1 = ( a[j] * b[i] - a[i] * b[j] ) / ( a[i] * a[i] * a[j] - a[j] * a[j] * a[i] );
if( ans1 < 0 ){
cnt ++;
sum[cnt]|= ( 1 << ( i - 1 ) ) , sum[cnt]|= ( 1 << ( j - 1 ) );
for( int k = 1 ; k <= n ; k ++ ){
if( k == i || k == j ) continue;
if( a[j] * a[j] * a[k] - a[k] * a[k] * a[j] == 0 ) continue;
double ans2 = ( a[k] * b[j] - a[j] * b[k] ) / ( a[j] * a[j] * a[k] - a[k] * a[k] * a[j] );
double t = ans1;
if( t < ans2 ) swap( t , ans2 );
if( t - ans2 < 1e-6 )
sum[cnt] |= ( 1 << ( k - 1 ) );
}
}
}
}
dp[0] = 0;
for( int i = 0 ; i < ( 1 << n ) ; i ++ ){
for( int j = 1 ; j <= cnt ; j ++ ){
int o = i | sum[j];
dp[o] = min( dp[i] + 1 , dp[o] );
}
}
printf( "%d\n" , dp[( 1<<n)-1] );
}
return 0;
}
————————————————————————————————————————————————————————
總結
狀壓刷表填表要靈活應用
(下面還有)
可是還沒有完，理論上來說
是不可以過的，有其他方法嗎？
還需要對狀壓dp進行優化
如果找到目前狀态點集S，準備去更新其它狀态
那麼找到x 滿足 S & ( 1 << ( x -1) ) == 0的最小正整數
那麼S所去更新的狀态一定要包括x，否則以後的狀态還要回來找經過x的抛物線，就多餘了
是以先預處理x，再枚舉與x所形成的抛物線的點集P
再用S去更新P+S
#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int MAXN = 20;
int n , m , T;
int dp[1<<MAXN];
int sum[MAXN][MAXN], cnt;
double a[MAXN] , b[MAXN];
int fu[1<<MAXN];
int main()
{
for( int i = 0 ; i < ( 1 << 18 ) ; i ++ ){
for( int j = 1 ; j <= 18 ; j ++ )
if( ( i & ( 1 << (j-1) ) )== 0 ){
fu[i] = j;
break;
}
if( !fu[i] )
fu[i] = 18;
}
scanf( "%d" , &T );
while( T -- ){
scanf( "%d%d" , &n , &m );
memset( sum , 0 , sizeof( sum ) );
memset( dp , 0x3f, sizeof( dp ) );
for( int i = 1 ; i <= n ; i ++ ){
scanf( "%lf%lf" , &a[i] , &b[i] );
}
for( int i = 1 ; i <= n ; i++ ){
for( int j = 1 ; j <= n ; j ++ ){
if( i ==j ) continue;
if( a[i] * a[i] * a[j] - a[j] * a[j] * a[i] == 0 ) continue;
double ans1 = ( a[j] * b[i] - a[i] * b[j] ) / ( a[i] * a[i] * a[j] - a[j] * a[j] * a[i] );
if( ans1 < 0 ){
sum[i][j]|= ( 1 << ( i - 1 ) ) , sum[i][j]|= ( 1 << ( j - 1 ) );
for( int k = 1 ; k <= n ; k ++ ){
if( k == i || k == j ) continue;
if( a[j] * a[j] * a[k] - a[k] * a[k] * a[j] == 0 ) continue;
double ans2 = ( a[k] * b[j] - a[j] * b[k] ) / ( a[j] * a[j] * a[k] - a[k] * a[k] * a[j] );
double t = ans1;
if( t < ans2 ) swap( t , ans2 );
if( t - ans2 < 1e-8 )
sum[i][j] |= ( 1 << ( k - 1 ) );
}
}
}
}
dp[0] = 0;
for( int i = 0 ; i < ( 1 << n ) ; i ++ ){
int j = fu[i];
dp[i|( 1 <<(j-1))] = min( dp[i|( 1 <<(j-1) )] , dp[i] + 1 );
for( int k = 1 ; k <= n ; k ++ ){
if( sum[j][k] )
dp[i|sum[j][k]] = min( dp[i] + 1 , dp[i|sum[j][k]] );
}
}
printf( "%d\n" , dp[( 1<<n)-1] );
}
return 0;
}