自动搬运

查看原文

来自洛谷，原作者为

	VenusM1nT 醉后不知天在水 满船清梦压星河 | 明日方舟群 348956527

搬运于2025-08-24 21:30:39，当前版本为作者最后更新于2018-12-21 16:03:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

古代评测姬怎么比现在快那么多啊QAQ

啊算了不管了

这道题……和P4537 [CQOI2007]矩形基本一模一样，但是这道题每种不同的分割方式，如果把黑白颜色交换是不同的方式，所以做法就是两趟爆搜分界线，从左侧和下侧开始爆搜，然后答案乘上$2$

此时你会光荣的收到$TLE\times 3$，但是这道题因为是一道计数的爆搜题，所以基本上应该是没有办法剪枝的，于是我们此时除了开$O2$（不知道能不能$AC$）还有什么办法呢？

回头看看数据范围，$n\leq 7,m\leq 8$，想到了什么？

没错，打表啊！

于是我们打表即可$AC$~

（注意，$(7,8)$这组极限数据要开$long\ long$）

打表程序：

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long ans;
int dx[]={0,1,-1,0,0},dy[]={0,0,0,1,-1};
bool vis[15][15];
void Dfs(int x,int y)
{
	if(x<1 || x>=n || y<1 || y>=m) ans++;
	else
	{
		vis[x][y]=1;
		for(int i=1;i<=4;i++)
		{
			int nx=x+dx[i],ny=y+dy[i];
			if(!vis[nx][ny]) Dfs(nx,ny);
		}
		vis[x][y]=0;
	}
}
int main()
{
	freopen("1.txt","r",stdin);
	freopen("ans2.txt","w",stdout);
	while(cin>>n>>m)
	{
		ans=0;
		for(int i=1;i<n;i++)
		{
			memset(vis,0,sizeof(vis));
			vis[i][0]=1;
			Dfs(i,1);
		}
		for(int i=1;i<m;i++)
		{
			memset(vis,0,sizeof(vis));
			vis[0][i]=1;
			Dfs(1,i);
		}
		printf("    else if(n==%d && m==%d) cout<<\"%lld\"<<endl;\n",n,m,ans*2);
	}
	return 0;
}

$AC$程序：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int main()
{
	scanf("%d %d",&n,&m);
	if(!n || !m) cout<<"0"<<endl;
    else if(n==1 && m==1) cout<<"0"<<endl;
    else if(n==1 && m==2) cout<<"2"<<endl;
    else if(n==1 && m==3) cout<<"4"<<endl;
    else if(n==1 && m==4) cout<<"6"<<endl;
    else if(n==1 && m==5) cout<<"8"<<endl;
    else if(n==1 && m==6) cout<<"10"<<endl;
    else if(n==1 && m==7) cout<<"12"<<endl;
    else if(n==1 && m==8) cout<<"14"<<endl;
    else if(n==2 && m==1) cout<<"2"<<endl;
    else if(n==2 && m==2) cout<<"12"<<endl;
    else if(n==2 && m==3) cout<<"30"<<endl;
    else if(n==2 && m==4) cout<<"56"<<endl;
    else if(n==2 && m==5) cout<<"90"<<endl;
    else if(n==2 && m==6) cout<<"132"<<endl;
    else if(n==2 && m==7) cout<<"182"<<endl;
    else if(n==2 && m==8) cout<<"240"<<endl;
    else if(n==3 && m==1) cout<<"4"<<endl;
    else if(n==3 && m==2) cout<<"30"<<endl;
    else if(n==3 && m==3) cout<<"104"<<endl;
    else if(n==3 && m==4) cout<<"286"<<endl;
    else if(n==3 && m==5) cout<<"700"<<endl;
    else if(n==3 && m==6) cout<<"1598"<<endl;
    else if(n==3 && m==7) cout<<"3488"<<endl;
    else if(n==3 && m==8) cout<<"7390"<<endl;
    else if(n==4 && m==1) cout<<"6"<<endl;
    else if(n==4 && m==2) cout<<"56"<<endl;
    else if(n==4 && m==3) cout<<"286"<<endl;
    else if(n==4 && m==4) cout<<"1228"<<endl;
    else if(n==4 && m==5) cout<<"4862"<<endl;
    else if(n==4 && m==6) cout<<"18368"<<endl;
    else if(n==4 && m==7) cout<<"67206"<<endl;
    else if(n==4 && m==8) cout<<"240180"<<endl;
    else if(n==5 && m==1) cout<<"8"<<endl;
    else if(n==5 && m==2) cout<<"90"<<endl;
    else if(n==5 && m==3) cout<<"700"<<endl;
    else if(n==5 && m==4) cout<<"4862"<<endl;
    else if(n==5 && m==5) cout<<"32000"<<endl;
    else if(n==5 && m==6) cout<<"204294"<<endl;
    else if(n==5 && m==7) cout<<"1274660"<<endl;
    else if(n==5 && m==8) cout<<"7807790"<<endl;
    else if(n==6 && m==1) cout<<"10"<<endl;
    else if(n==6 && m==2) cout<<"132"<<endl;
    else if(n==6 && m==3) cout<<"1598"<<endl;
    else if(n==6 && m==4) cout<<"18368"<<endl;
    else if(n==6 && m==5) cout<<"204294"<<endl;
    else if(n==6 && m==6) cout<<"2228788"<<endl;
    else if(n==6 && m==7) cout<<"23896710"<<endl;
    else if(n==6 && m==8) cout<<"252488208"<<endl;
    else if(n==7 && m==1) cout<<"12"<<endl;
    else if(n==7 && m==2) cout<<"182"<<endl;
    else if(n==7 && m==3) cout<<"3488"<<endl;
    else if(n==7 && m==4) cout<<"67206"<<endl;
    else if(n==7 && m==5) cout<<"1274660"<<endl;
    else if(n==7 && m==6) cout<<"23896710"<<endl;
    else if(n==7 && m==7) cout<<"441524056"<<endl;
    else if(n==7 && m==8) cout<<"8056291934"<<endl;
    return 0;
}