程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> sgu262:Symbol Recognition(狀壓DP)

sgu262:Symbol Recognition(狀壓DP)

編輯:C++入門知識

sgu262:Symbol Recognition(狀壓DP)


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

分析:
這題有幾個狀壓DP的思路,這裡講一個吧。
假設我們將SiP的交定義為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;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved