hdu1693-Eat the Trees

題目

一個方格圖，有一些點是障礙，求有用一些回路精确覆寫非障礙點的方案數。\(n,m\le 11\)

分析

開始學插頭dp，這是第一題。

這其實可以說是一個輪廓線dp，因為可以用多個回路，是以無須儲存其他的連通性狀态，隻要記錄從上到下，從左到右dp到每一個點的時候每一種插頭情況的方案數，一個個轉移即可。畫一下圖就知道了。

最開始糾結的是初始化問題。其實為了代碼友善，可以初始化

f[0][m][0]=1

，這樣在處理換行的時候就會自動把這個順延到第一行。換行處理就左移一下，因為前一行的最後一個（右插頭）和目前行的第一個（右插頭）必定是空的。

代碼

#include<bits/stdc++.h>
using namespace std;
typedef long long giant;
inline giant read() {
    giant x=0,f=1;
    char c=getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
    for (;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
const giant maxn=12;
const giant maxs=1<<maxn;
giant f[maxn][maxn][maxs];
bool a[maxn][maxn];
int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in","r",stdin);
#endif
    giant T=read(),cas=0;
    while (T--) {
        memset(f,0,sizeof f);
        giant n=read(),m=read(),s=1<<(m+1);
        for (giant i=1;i<=n;++i) for (giant j=1;j<=m;++j) a[i][j]=read();
        f[0][m][0]=1;
        for (giant i=1;i<=n;++i) {
            for (giant k=0;k<(1<<m);++k) f[i][0][k<<1]=f[i-1][m][k];
            for (giant j=1;j<=m;++j) {
                for (giant k=0;k<s;++k) {
                    bool lef=((k>>(j-1))&1),up=((k>>j)&1);
                    giant x=(1<<(j-1))|(1<<j);
                    if (!a[i][j]) {
                        if (!lef && !up) f[i][j][k]+=f[i][j-1][k];
                    } else if (lef^up) f[i][j][k]+=f[i][j-1][k],f[i][j][k^x]+=f[i][j-1][k]; else f[i][j][k^x]+=f[i][j-1][k];
                }
            }
        }
        printf("Case %lld: There are %lld ways to eat the trees.\n",++cas,f[n][m][0]);
    }
    return 0;
}                

轉載于:https://www.cnblogs.com/owenyu/p/7279468.html