程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> sgu262：Symbol Recognition(狀壓DP)

sgu262：Symbol Recognition(狀壓DP)

編輯：關於C++

題目大意：
給出k個n?m的01矩陣Si，求出一個1盡量少的n?m的01矩陣P，滿足k個矩陣與該矩陣的交互不相同，也就是說通過該矩陣能表示出給出的k個矩陣。

分析：
這題有幾個狀壓DP的思路，這裡講一個吧。
假設我們將Si與P的交定義為Qi，其編號為Ti，那麼初始的時候交都為空，即T1=T2=...=Tk=0，Q1=Q2=...=Qk=?。
枚舉P當前的格子(x,y)，假設有Si,x,y=Sj,x,y=1，且Qi=Qj，那麼當前格子放1的話，新的Qi依舊等於Qj，反之不等於。所以可以用最小表示搞出該格子放1後的T。然而T就是整個狀壓DP的狀態。當max{Ti}=k?1的時候，證明所有的Ti均不相同，也就是所有的Qi均不相同，此時的P即為所求。

AC code：

#include 
#include 
#include
#define pii pair
#define mp make_pair
using namespace std;

const int MAXK = 7;
const int MAXN = 11;
const int MAXS = 46660;
const int INF = 0x3f;

int n, m, k, s;
int g[MAXK][MAXN][MAXN];
int col[MAXN][MAXN];
int f[MAXS], fr[MAXS], fx[MAXS], fy[MAXS];
map S;
int ans[MAXN][MAXN];

void upd(int s, int x, int y)
{
    int ts = s, add = f[s], tot = 0, ns = 0;
    pii sta[MAXK];S.clear();
    for(int i = 0, j = 1; i < k; ++i, ts /= k, j *= k)
    {
        sta[i] = mp(ts%k, g[i][x][y]);
        if(!S.count(sta[i])) S[sta[i]] = tot++;
        ns += S[sta[i]]*j;
    }
    if(f[ns] > add+1)
    {
        f[ns] = add+1, fr[ns] = s;
        fx[ns] = x, fy[ns] = y;
    }
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif

    scanf("%d%d%d", &n, &m, &k);
    for(int i = 0; i < k; ++i)
        for(int p = 0; p < n; ++p)
            for(int q = 0; q < m; ++q)
            {
                scanf("%1d", &g[i][p][q]);
                col[p][q] |= g[i][p][q];    
            }
    s = 1;
    for(int i = 0; i < k; ++i) s *= k;
    memset(f, INF, sizeof f);
    f[0] = 0;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            if(col[i][j])
                for(int p = 0; p < s; ++p)
                    if(f[p] < INF)
                        upd(p, i, j);
    int end = 0;
    for(int i = k-1; i >= 0; --i)
        end = end*k+i;
    printf("%d\n", f[end]);
    int now = end;
    while(now)
    {
        ans[fx[now]][fy[now]] = 1;
        now = fr[now];
    }   
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < m; ++j)
            printf("%d", ans[i][j]);
        puts("");   
    }

    #ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    #endif  
    return 0;
}