```cpp
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#define N 10
using namespace std;
int a[N][N],tot,ans,res;
int bx[N*N],by[N*N],nxt,hyf;
int zer[N];
struct ptn{
int x,y;
}b[N*N];
int v[N][N]={
{0,0,0,0,0,0,0,0,0,0},
{0,6,6,6,6,6,6,6,6,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,9,10,9,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,6,6,6,6,6,6,6,6},
};
int bel[N][N]={
{0,0,0,0,0,0,0,0,0,0},
{0,1,1,1,2,2,2,3,3,3},
{0,1,1,1,2,2,2,3,3,3},
{0,1,1,1,2,2,2,3,3,3},
{0,4,4,4,5,5,5,6,6,6},
{0,4,4,4,5,5,5,6,6,6},
{0,4,4,4,5,5,5,6,6,6},
{0,7,7,7,8,8,8,9,9,9},
{0,7,7,7,8,8,8,9,9,9},
{0,7,7,7,8,8,8,9,9,9},
};
int tx[N][N]={
{0,0,0,0,0,0,0,0,0,0},
{0,1,1,1,1,1,1,1,1,1},
{0,1,1,1,1,1,1,1,1,1},
{0,1,1,1,1,1,1,1,1,1},
{0,4,4,4,4,4,4,4,4,4},
{0,4,4,4,4,4,4,4,4,4},
{0,4,4,4,4,4,4,4,4,4},
{0,7,7,7,7,7,7,7,7,7},
{0,7,7,7,7,7,7,7,7,7},
{0,7,7,7,7,7,7,7,7,7},
};
int cnt1[N][N];
int cnt2[N][N];
int cnt3[N][N];
inline bool cmp(ptn a,ptn b){
return zer[a.x]<zer[b.x];
}
inline bool check(int x,int y){
if(cnt1[x][a[x][y]]>=2)return 0;
if(cnt2[y][a[x][y]]>=2)return 0;
if(cnt3[bel[x][y]][a[x][y]]>=2)return 0;
return 1;
}
inline void dfs(int q){
if(b[q].x&&b[q].y&&(!check(b[q].x,b[q].y)))return;
if(q>=nxt){
ans=max(ans,res);
return;
}
int xx=b[q+1].x,yy=b[q+1].y;
for(int j=9;j>=1;j--){
a[xx][yy]=j;
cnt1[xx][a[xx][yy]]++;
cnt2[yy][a[xx][yy]]++;
cnt3[bel[xx][yy]][a[xx][yy]]++;
tot++;
res+=v[xx][yy]*j;
dfs(q+1);
tot--;
res-=v[xx][yy]*j;
cnt1[xx][a[xx][yy]]--;
cnt2[yy][a[xx][yy]]--;
cnt3[bel[xx][yy]][a[xx][yy]]--;
a[xx][yy]=0;
}
}
signed main(){
for(int i=1;i<=9;i++){
for(int j=1;j<=9;j++){
scanf("%d",&a[i][j]);
if(a[i][j]){
tot++,res+=v[i][j]*a[i][j];
int xx=i,yy=j;
cnt1[xx][a[xx][yy]]++;
cnt2[yy][a[xx][yy]]++;
cnt3[bel[xx][yy]][a[xx][yy]]++;
}
if(!a[i][j])b[++nxt]=(ptn){i,j},zer[i]++;
}
}
sort(b+1,b+nxt+1,cmp);
dfs(0);
if(ans==0)puts("-1");
else printf("%d",ans);
return 0;
}
```
实在剪纸剪不动了
by 黑影洞人 @ 2022-10-28 21:24:50
教您一绝招
## 极限弹出(好像是这么叫的叫错了不要喷谢谢)
就是卡常
每运行一次dfs函数ct++
实测ct<=1e7+6e5再吸个氧(其实可以不吸,也能AC)跑得飞快,可以AC
~~真·数据水~~
by chensiming_2022 @ 2022-12-31 14:42:33
当然您的代码与我不同,附上AC代码(不吸痒的,1000ms内通过)
```cpp
#include<bits/stdc++.h>
#define min(a,b) (a>b?b:a)
#define max(a,b) (a<b?b:a)
int have[13][13],ans=-1,kkk;
int ct,yx[87][3],cnt;
bool hang[13][13],lie[13][13],gong[17][13];
inline int jiazhi(int x,int y){
int o=min(min(x,10-x),min(y,10-y));
return o+5;
}
inline int getgong(int x,int y){
int nx=(x-1)/3,ny=(y-1)/3+1;
return nx*3+ny;
}
inline bool pd(int x,int y,int i){return !hang[x][i]&&!lie[y][i]&&!gong[getgong(x,y)][i];}
inline void fz(int x,int y,int i,bool s){hang[x][i]=lie[y][i]=gong[getgong(x,y)][i]=s;}
inline void dfs(int n,int sum){
if(++ct>=(1e7+6e5))
return;
if(n<=0){
ans=max(sum,ans);
return;
}
int x=n/9+((n%9)>0),y=((n%9)>0)?(n%9):9;
if(have[x][y])
dfs(n-1,sum);
else
for(int i=1;i<=9;i++)
if(pd(x,y,i)){
fz(x,y,i,1);
dfs(n-1,sum+i*jiazhi(x,y));
fz(x,y,i,0);
}
}
int main(){
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++){
scanf("%d",have[i]+j),kkk+=have[i][j]*jiazhi(i,j);
if(have[i][j])
fz(i,j,have[i][j],1);
}
dfs(81,kkk);
printf("%d",ans);
return 0;
}
```
AC记录:https://www.luogu.com.cn/record/98341709\
![全部绿油油](https://img-blog.csdnimg.cn/5276e5ef3ebe49cdad951032ddfd62b3.png)
by chensiming_2022 @ 2022-12-31 14:49:05
@[黑影洞人](/user/285617) 多加几个 `inline` 和 `register`也行。
by Nuclear_Pasta @ 2023-04-06 17:15:25