Light OJ 1018 的额加强版
  • 板块题目总版
  • 楼主THUHS_Finder
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/8/2 14:19
  • 上次更新2023/11/4 12:14:20
查看原帖
Light OJ 1018 的额加强版
231641
THUHS_Finder楼主2021/8/2 14:19

这个代码怎么去重/kel

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int x[20], y[20];
int dp[1<<16], line[20][20];
vector <int> p[1<<16];
void init()
{
    for(int i=0;i<(1<<16);i=-~i)
    {
        for(int j=0;j<16;j=-~j)
        {
            if((i&(1<<j))) continue;
            p[i].push_back(j);
        }
    }
}
inline int check(int i,int j,int k)
{
    int y2=y[j];
	int y1=y[i];
	int y3=y[k];
    int x2=x[j];
	int x1=x[i];
	int x3=x[k];
    if(y3*(x2-x1)==(y2-y1)*x3+x2*y1-x1*y2) return 1;
    else return 0;
}
void pre(int n)
{
	for(int i=0;i<n;i++)
    {
        line[i][i]=(1<<i);
        for(int j=i+1;j<n;j++)
        {
            for(int k=0;k<n;k++)
            {
                if(check(i,j,k)) line[i][j]|=(1<<k);
            }
        }
	}
}
int main()
{
	int T,n;
	cin>>T;	
    init();
    while(T--)
    {
        cin>>n;
        for(int i=0;i<n;i++)cin>>x[i]>>y[i];
        memset(dp,INF,sizeof(dp));
        memset(line,0,sizeof(line));
        pre(n);
        dp[0]=0;
        for(int i=0;i<(1<<n)-1;i++)
        {
            int x=p[i][0];
            for(int j=0;j<p[i].size();j++)
            {
                int y=p[i][j];
                dp[i|line[x][y]]=min(dp[i|line[x][y]],dp[i]+1);
                //break;
            }
            break;
        }
        cout<<dp[(1<<n)-1]<<endl;
    }
    return 0;
}
2021/8/2 14:19
加载中...