(轮廓线) 必须用滚动数组?
查看原帖
(轮廓线) 必须用滚动数组?
551417
CommonDigger楼主2024/12/1 11:49

下面这份代码没有使用滚动数组,不能过样例,改成滚动就过了为什么?

#include "iostream"
#include "cstring"
using namespace std;
int n, m, temp, q;
unsigned long long f[10][1024];
int main(){
//    ios::sync_with_stdio(0);
//    cin.tie(0);
//    cout.tie(0);
    while(cin >> n >> m){
        if(m>n) swap(m, n);
        temp=1<<m;
        memset(f, 0, sizeof(f));
        f[0][temp-1]=1;
        for(int i=0;i<n;i++){
            for(int j=1;j<=m;j++){
                for(int x=0;x<temp;x++){ // x: 当前轮廓
                    if(x&(1<<(j-1))){ // 这一位上面是 1
                        // 不放
                        f[j][x^(1<<(j-1))]+=f[j-1][x];
                        if(j>1 && !(x&(1<<(j-2)))){ // 左边是0
                            f[j][x|(1<<(j-2))]+=f[j-1][x];
                        }
                    }else{ // 上面是0,竖置
                        if(i) f[j][x|(1<<(j-1))]+=f[j-1][x];
                    }
                }
            }
        }
        cout << f[m-1][temp-1] << "\n";
    }
}
2024/12/1 11:49
加载中...