如题,拉差只能在模意义下做吗
#include<bits/stdc++.h>
using namespace std;
int T;
int n,m;
int dp[1<<18],lim[25][25];
namespace Lagrange{
double a[3],f[3];
inline double solve(int k){
double res=0;
for(int i=0;i<3;i++){
double tmp=f[i];
for(int j=0;j<3;j++){
if(i!=j)tmp*=(a[j]-k)/(a[j]-a[i]);
}res=res+tmp;
}//cout<<res<<endl;
return res;
}
}
using Lagrange::solve;
using Lagrange::a;
using Lagrange::f;
double x[25],y[25];
inline void init(int i,int j){
if(i==j){lim[i][j]=(1<<i);return ;}
lim[i][j]=0;
a[1]=x[i];a[2]=x[j];f[1]=y[i];f[2]=y[j];
for(int t=0;t<n;t++)if(fabs(solve(x[t])-y[t])<=1e-6)lim[i][j]|=(1<<t);
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++){
scanf("%lf%lf",&x[i],&y[i]);
}
memset(dp,0x3f,sizeof(dp));dp[0]=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)init(i,j);//,cout<<i<<" "<<j<<" :"<<lim[i][j]<<endl;;
}
for(int s=0;s<(1<<n)-1;s++){
int j=0;while((s>>j)&1)j++;
for(int t=0;t<n;t++)dp[s|lim[j][t]]=min(dp[s|lim[j][t]],dp[s]+1);
}printf("%d\n",dp[(1<<n)-1]);
}
return 0;
}
还是说我哪里写挂了