蒟蒻求助 DLX TLE!!!
查看原帖
蒟蒻求助 DLX TLE!!!
464004
ZepX_D楼主2024/8/21 19:32

What can I say?

#include <bits/stdc++.h>
#define pb push_back
#define LL long long

using namespace std;

inline int read()
{
	int x = 0;char ch = getchar();
	while(!isdigit(ch)) ch = getchar();
	while(isdigit(ch)) x = x*10+ch-48,ch = getchar();
	return x;
}
int v[10][10] = {{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}};
const int M = 2920;
int siz[330],h[733],l[M],r[M],u[M],d[M],row[M],col[M],cnt;

inline void build(int m)
{
	for (int i = 0;i <= m;i++)
		l[i] = i-1,r[i] = i+1,u[i] = d[i] = i;
	l[0] = m,r[m] = 0;
	cnt = m;
}

inline void ins(int R,int C)
{
	siz[C]++,cnt++;
	row[cnt] = R,col[cnt] = C;
	u[cnt] = C,d[cnt] = d[C];
	u[d[C]] = cnt,d[C] = cnt;
	if(!h[R]) h[R] = l[cnt] = r[cnt] = cnt;
	else
	{
		r[cnt] = h[R],l[cnt] = l[h[R]];
		r[l[h[R]]] = cnt,l[h[R]] = cnt;
	}
}

inline void remove(int C)
{
	r[l[C]] = r[C],l[r[C]] = l[C];
	for (int i = d[C];i != C;i = d[i])
		for (int j = r[i];j != i;j = r[j])
			u[d[j]] = u[j],d[u[j]] = d[j],siz[C]--;
}

inline void recover(int C)
{
	for (int i = u[C];i != C;i = u[i])
		for (int j = l[i];j != i;j = l[j])
			u[d[j]] = d[u[j]] = j,siz[C]++;
	r[l[C]] = l[r[C]] = C;
}

int s[M],ans;

void dance(int dep)
{
	if(!r[0])
	{
		int res = 0;
		for (int i = 1;i <= dep;i++)
		{
			int x = (s[i]-1)/9/9+1,y = (s[i]-1)/9%9+1,val = (s[i]-1)%9+1;
			res += v[x][y]*val;
		}
		ans = max(ans,res);
		return ;
	}
	int C = r[0];
	for (int i = r[0];i;i = r[i])
		if(siz[i] < siz[C]) C = i;
	remove(C);
	for (int i = d[C];i != C;i = d[i])
	{
		s[dep+1] = row[i];
		for (int j = r[i];j != i;j = r[j]) remove(col[j]);
		dance(dep+1);
		for (int j = l[i];j != i;j = l[j]) recover(col[j]);
	}
	recover(C);
}

void Ins(int r,int c,int k)
{
	int ro = (r-1)*81+(c-1)*9+k;
	int x = (r-1)/3+1,y = (c-1)/3+1,id = (x-1)*3+y;
	int f1 = (r-1)*9+c,f2 = 81+(r-1)*9+k,f3 = 81*2+(c-1)*9+k,f4 = 81*3+(id-1)*9+k;
	ins(ro,f1),ins(ro,f2),ins(ro,f3),ins(ro,f4);
}

int main()
{
	build(324);
	int sum = 0;
	for(int i = 1;i <= 9;i++)
	{
		for (int j = 1,x;j <= 9;j++)
		{
			x = read();
			if(x) Ins(i,j,x);
			else for (int k = 1;k <= 9;k++) Ins(i,j,k);
		}
	}
	dance(0);
	cout << (ans ? ans : -1);
	return 0;
}
2024/8/21 19:32
加载中...