P8488 「Wdoi-(-1)」恋弹者们的黑集市

· · 题解

思路

设 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);
}