这份代码是 O(n×2m×(n+m)) 的,但没有 TLE。是我算错了吗?求大佬们指教,谢谢。记录。
#include<bits/stdc++.h>
using namespace std;
int n,m,a[21][21],t[21],ans,cnt,p0;
struct node{
int zhi,g;
}p[1<<20];
bool tp[21];
int count(int p){
int res=0;
while(p){
p-=(p&(-p));
++res;
}
return res;
}
bool cmp(node x,node y){
return x.g<y.g;
}
int main(){
scanf("%d%d",&n,&m);
if(n==1){
puts("0");
return 0;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
}
}
bool flag;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j){
continue;
}
flag=0;
for(int k=1;k<=m;k++){
if(a[i][k]!=a[j][k]){
flag=1;
break;
}
}
if(!flag){
tp[i]=tp[j]=1;
}
}
}
for(int i=1;i<(1<<m);i++){
p[++p0].zhi=i;
p[p0].g=count(i);
}
sort(p+1,p+p0+1,cmp);
for(int i=1;i<=n;i++){
if(tp[i]){
printf("%d ",-1);
continue;
}
ans=INT_MAX,cnt;
for(int j1=1;j1<=p0;j1++){
int j=p[j1].zhi;
cnt=0;
for(int k=1;k<=n;k++){
t[k]=0;
}
for(int k=1;k<=m;k++){
if((1<<(k-1))&j){
++cnt;
for(int l=1;l<=n;l++){
if(i!=l&&a[i][k]==a[l][k]){
++t[l];
}
}
}
}
for(int k=1;k<=n;k++){
if(t[k]==cnt){
break;
}
if(k==n){
ans=cnt;
}
}
if(ans!=INT_MAX){
break;
}
}
if(ans==INT_MAX){
printf("%d ",-1);
}
else{
printf("%d ",ans);
}
}
putchar('\n');
return 0;
}