5000ms+跑过...
by iodwad @ 2017-10-22 20:47:47
@[ZCDHJ](/space/show?uid=24878) 然而时限1s(雾
by Heartbeat666 @ 2017-10-22 20:50:02
@[Heartbeat666](/space/show?uid=17142) 233333我知道啊
by iodwad @ 2017-10-22 20:57:01
@[ZCDHJ](/space/show?uid=24878) 按题目所说 这题其实不可做 DLX似乎也没用
by Heartbeat666 @ 2017-10-22 21:00:28
@[ZCDHJ](/space/show?uid=24878) 膜拜。。。
by waterlike @ 2018-04-29 20:13:41
这个呢
```
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
```
by ktSS @ 2018-05-12 17:02:41
本机30ms*1000.............
by Rising_Down @ 2018-05-17 20:29:52
@[We_luogu](/space/show?uid=24255) 可以用
**数学方法**
解决
by ererer @ 2018-05-18 08:27:56
@[ZCDHJ](/space/show?uid=24878) 我也5000+ms
by ererer @ 2018-05-18 08:30:49
@[Heartbeat666](/space/show?uid=17142) 某神犇代码0.1ms跑过。。。
```cpp
#include<bits/stdc++.h>
using namespace std;
struct Node{short x,y,v;}w[128];
short can_get[128];
inline bool cmp(const Node &a,const Node &b){
if(a.v/9!=b.v/9) return a.v<b.v;
if(a.x!=b.x) return a.x<b.x;
return a.v<b.v;
}
short zt[16][4];
short done[16][16],be[16][16];
short fz[16][16]={
{6,6,6,6,6,6,6,6,6},
{6,7,7,7,7,7,7,7,6},
{6,7,8,8,8,8,8,7,6},
{6,7,8,9,9,9,8,7,6},
{6,7,8,9,10,9,8,7,6},
{6,7,8,9,9,9,8,7,6},
{6,7,8,8,8,8,8,7,6},
{6,7,7,7,7,7,7,7,6},
{6,6,6,6,6,6,6,6,6},
};
short qz[16][16];
short nex[1024],pre[1024];
int bes,now,bs;
inline void dfs(register int p){
if(p==81){
bes=max(bes,now);
return;
}
if(done[w[p].x][w[p].y]){
now+=fz[w[p].x][w[p].y]*done[w[p].x][w[p].y];
dfs(p+1);
return;
}
if((can_get[p]<<3)+can_get[p]+now<=bes) return;
++bs;
if(bs>=1900000) return;
register int x=w[p].x,y=w[p].y,bel=be[x][y],can_use=zt[x][0]&zt[y][1]&zt[bel][2],t,z;
if(fz[x][y]<=6){
while(can_use){
t=pre[can_use];
z=(1<<t);
zt[x][0]^=z;
zt[y][1]^=z;
zt[bel][2]^=z;
now+=fz[x][y]*(t+1);
dfs(p+1);
now-=fz[x][y]*(t+1);
zt[x][0]^=z;
zt[y][1]^=z;
zt[bel][2]^=z;
can_use^=z;
}
}
else{
while(can_use){
t=nex[can_use];
z=(1<<t);
zt[x][0]^=z;
zt[y][1]^=z;
zt[bel][2]^=z;
now+=fz[x][y]*(t+1);
dfs(p+1);
now-=fz[x][y]*(t+1);
zt[x][0]^=z;
zt[y][1]^=z;
zt[bel][2]^=z;
can_use^=z;
}
}
}
int main(){
for(register int i=0;i<9;i++)
for(register int j=0;j<3;j++)
zt[i][j]=(1<<9)-1;
for(register int i=0;i<9;i++)
for(register int j=0;j<9;j++)
scanf("%d",&done[i][j]);
for(register int i=0;i<9;i++){
for(register int j=0;j<i;j++){
swap(done[i][j],done[j][i]);
}
}
for(register int i=0;i<9;i++)
for(register int j=0;j<9;j++){
register int a=done[i][j];
if(!a) continue;
a--;
zt[i][0]-=(1<<a);
zt[j][1]-=(1<<a);
zt[(i/3)*3+j/3][2]-=(1<<a);
}
for(register int i=0;i<9;i++){
for(register int j=0;j<9;j++){
register int can_use=zt[i][0]&zt[j][1]&zt[(i/3)*3+j/3][2];
w[i*9+j].x=i,w[i*9+j].y=j;
if(done[i][j]) w[i*9+j].v=0;
else{
for(register int l=0;l<9;l++){
if((1<<l)&zt[i][0]) w[i*9+j].v+=9;
}
for(register int l=0;l<9;l++){
if((1<<l)&can_use) w[i*9+j].v++;
}
}
be[i][j]=(i/3)*3+j/3;
}
}
sort(w,w+81,cmp);
for(register int i=80;i>=0;i--){
can_get[i]=can_get[i+1]+fz[w[i].x][w[i].y];
}
for(register int i=1;i<(1<<9);i++){
for(register int j=0;j<9;j++)
if((1<<j)&i) nex[i]=j;
for(register int j=8;j>=0;j--)
if((1<<j)&i) pre[i]=j;
}
dfs(0);
if(bes==0) puts("-1");
else printf("%d\n",bes);
return 0;
}
```
by waterlike @ 2018-11-06 20:19:17