自动搬运

查看原文

来自洛谷，原作者为

	•́へ•́╬ Unsuccessful Leaving Something attempt

搬运于2025-08-24 22:39:31，当前版本为作者最后更新于2022-08-23 19:16:54，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路

设 $f[i][j][?]$ 表示正方体滚到 $(i,j)$，且正方体的状态（朝向）为 ? 的答案。

如何表示正方体的状态？

小学奥数初中数学我们学过三视图。

对于本题，我们记录三个方向即可。

我的代码中：$[o][p][q]$ 为下面（贴着棋盘的那个）是 $o$，正对着你的（往 $(i+1,j)$ 翻转就贴着地的那个）是 $p$，右边的（往 $(i,j+1)$ 翻转就贴着地的那个）是 $q$。

判断状态合法：$o,p,q$ 必须是不同方向，也就是说既不能相同也不能相对。

貌似卡空间？用了滚动数组。

code

#include<stdio.h>
#include<string.h>
#define N 1000
inline char nc()
{
	static char buf[99999],*l,*r;
	return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
	bool t=0;char c=nc();for(;c<'0'||'9'<c;t|=c=='-',c=nc());
	for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());if(t)x=-x;
}
int n,m,a[N][N],f[2][N][6][6][6],w[6],ans=-(1<<30);
inline int max(const int&x,const int&y){return x>y?x:y;}
main()
{
	read(n);read(m);
	for(int i=0;i<n;++i)for(int j=0;j<m;read(a[i][j++]));
	for(int i=0;i<6;read(w[i++]));
	memset(f,0xbb,sizeof(f));
	f[0][0][5][0][3]=a[0][0]*w[5];
	for(int j=1;j<m;++j)for(int o=0;o<6;++o)for(int p=0;p<6;++p)
		if((o^p)&&(o^p^1))for(int q=0;q<6;++q)if((o^q)&&(o^q^1))
			if((p^q)&&(p^q^1))
				f[0][j][o][p][q]=f[0][j-1][q^1][p][o]+a[0][j]*w[o];//第一行
	for(int i=1;i<n;++i)
	{
		for(int o=0;o<6;++o)for(int p=0;p<6;++p)
			if((o^p)&&(o^p^1))for(int q=0;q<6;++q)if((o^q)&&(o^q^1))
				if((p^q)&&(p^q^1))
					f[i&1][0][o][p][q]=f[i&1^1][0][p^1][o][q]+a[i][0]*w[o];//第一列
		for(int j=1;j<m;++j)for(int o=0;o<6;++o)for(int p=0;p<6;++p)
			if((o^p)&&(o^p^1))for(int q=0;q<6;++q)if((o^q)&&(o^q^1))
				if((p^q)&&(p^q^1))
					f[i&1][j][o][p][q]=max(f[i&1][j-1][q^1][p][o],
						f[i&1^1][j][p^1][o][q])+a[i][j]*w[o];
	}
	for(int o=0;o<6;++o)for(int p=0;p<6;++p)if((o^p)&&(o^p^1))
		for(int q=0;q<6;++q)if((o^q)&&(o^q^1)&&(p^q)&&(p^q^1))
			ans=max(ans,f[n&1^1][m-1][o][p][q]);
	printf("%d",ans);
}