蒟蒻第二天调了,要吐了
查看原帖
蒟蒻第二天调了,要吐了
173660
zhoukangyang楼主2020/7/25 08:27

啊啊啊啊啊啊啊啊啊大佬们帮帮这个菜鸡看看吧QAQAQAQAQAQAQAQAQAQAQAQAQAQAQAQAQAQAQAQAQAQAQAQAQAQ

// 轮廓线dp
#include<bits/stdc++.h>

#define int long long
#define N 33

using namespace std;
int n, m, dp[2][N][N][N]; 

// dp: 滚动数组
// dp[][a][b][c] 存储了第一个L在轮廓线位置a , 第二个L在轮廓线位置b , 第三个L在轮廓线位置c
// 特别的,0 是没有出现过L,m+2 为已经处理完了 

char s[N][N];
signed main() {
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++) 
        scanf("%s",s[i]+1);
    dp[1][0][0][0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(s[i][j] == '#'){
                // 障碍转移:这里没有L才能转移
                for(int xa = m+2; xa >= 0; xa--) {
                    for(int xb = m+2; xb >= 0; xb--) {
                        for(int xc = m+2; xc >= 0; xc--) {
                            if((xa - j) * (xa - j - 1) == 0) continue;
                            if((xb - j) * (xb - j - 1) == 0) continue;
                            if((xc - j) * (xc - j - 1) == 0) continue;
                            dp[0][xa][xb][xc] = dp[1][xa][xb][xc];
                        }
                    }
                }
            }
            else { 
                // 普通转移
                for(int xa = m+2; xa >= 0; xa--) {
                    for(int xb = m+2; xb >= 0; xb--) {
                        for(int xc = m+2; xc >= 0; xc--) {
                            int fax = (xa == j), fay = (xa == j+1);
                            int fbx = (xb == j), fby = (xb == j+1);
                            int fcx = (xc == j), fcy = (xc == j+1);
                            int ds = dp[1][xa][xb][xc], Sum = fax + fay + fbx + fby + fcx + fcy;
                            
                            if(Sum == 0) dp[0][xa][xb][xc] += ds;
                            // 如果没有L,直接转移;

                            if(Sum != 1) continue;
                            // 有多于1个L或1个L出现两次,舍去
                            
                            if(fax) dp[0][xa][xb][xc] += dp[1][xa+1][xb][xc] + dp[1][0][xb][xc], dp[0][m+2][xb][xc] += ds;
                            if(fbx) dp[0][xa][xb][xc] += dp[1][xa][xb+1][xc] + dp[1][xa][0][xc], dp[0][xa][m+2][xc] += ds;
                            if(fcx) dp[0][xa][xb][xc] += dp[1][xa][xb][xc+1] + dp[1][xa][xb][0], dp[0][xa][xb][m+2] += ds;
                            if(fay) dp[0][xa][xb][xc] += ds + dp[1][xa-1][xb][xc];
                            if(fby) dp[0][xa][xb][xc] += ds + dp[1][xa][xb-1][xc];
                            if(fcy) dp[0][xa][xb][xc] += ds + dp[1][xa][xb][xc-1];
                            // 各种转移
                        }
                    }
                }
            }
            if(j == m) continue;
            for(int xa = m+2; xa >= 0; xa--)
                for(int xb = m+2; xb >= 0; xb--)
                    for(int xc = m+2; xc >= 0; xc--)
                        dp[1][xa][xb][xc] = dp[0][xa][xb][xc], dp[0][xa][xb][xc] = 0;
            // 数组滚动
        }
        for(int xa = m+2; xa >= 0; xa--) {
            for(int xb = m+2; xb >= 0; xb--) {
                for(int xc = m+2; xc >= 0; xc--) {
                    if(xa == m+1 || xb == m+1 || xc == m+1) continue;
                    if(xa == 1 || xb == 1 || xc == 1) continue;
                    int sa = xa, sb = xb, sc = xc;
                    if(xa != m+2 && xa != 0) sa++;
                    if(xb != m+2 && xb != 0) sb++;
                    if(xc != m+2 && xc != 0) sc++;
                    dp[1][sa][sb][sc] = dp[0][xa][xb][xc];
                }
            }
        }
        //轮廓在行中的转移,同一个轮廓要让L的下表增加1
        for(int xa = 0; xa <= m+2; xa++) 
            for(int xb = 0; xb <= m+2; xb++) 
                for(int xc = 0; xc <= m+2; xc++)
                    dp[0][xa][xb][xc] = 0;
        //数组滚动
    }
    printf("%lld\n", dp[1][m+2][m+2][m+2] / 6);
    //输出:由于对于同一种方案可以有6种组合,答案要 除以6
    return 0;
}

蒟蒻不希望看到无意义评论

过样例了,但只有 55 分qwq

2020/7/25 08:27
加载中...