Агуулгыг алгасах

Эвдэрсэн профиль дээрх динамик программчлал. "Паркет" бодлого

Эвдэрсэн профиль дээрх DP ашиглан бодогддог түгээмэл бодлогуудад:

  • ямар нэг талбайг (жишээ нь шатрын самбар/тор) ямар нэг дүрсээр (жишээ нь домино) бүрэн дүүргэх аргын тоог олох
  • талбайг хамгийн цөөн тооны дүрсээр дүүргэх аргыг олох
  • дүүргэгдээгүй зай (тор бол нүд) хамгийн цөөн байх хэсэгчилсэн дүүргэлтийг олох
  • өөр дүрс нэмэх боломжгүй байхаар хамгийн цөөн тооны дүрстэй хэсэгчилсэн дүүргэлтийг олох зэрэг орно

"Паркет" бодлого

Бодлогын тайлбар. $N \times M$ хэмжээтэй тор өгөгдсөн. Торыг $2 \times 1$ хэмжээтэй дүрсээр дүүргэх аргын тоог ол (ямар ч нүд дүүргэгдээгүй үлдэх ёсгүй бөгөөд дүрсүүд бие биетэйгээ давхцах ёсгүй).

DP төлөв нь $dp[i, mask]$ байг, энд $i = 1, \ldots N$ ба $mask = 0, \ldots 2^M - 1$.

$i$ нь одоогийн тор дахь мөрийн тоог илэрхийлэх ба $mask$ нь одоогийн торын сүүлийн мөрийн төлөв юм. Хэрэв $mask$-ийн $j$-р бит $0$ бол харгалзах нүд дүүргэгдсэн, эс бөгөөс дүүргэгдээгүй болно.

Бодлогын хариу нь $dp[N, 0]$ байх нь тодорхой.

Бид $i = 1, \cdots N$ бүр ба $mask = 0, \ldots 2^M - 1$ бүрээр давтаж DP төлвийг байгуулах ба $mask$ бүрийн хувьд бид зөвхөн урагш шилжинэ, өөрөөр хэлбэл одоогийн торонд дүрс нэмнэ.

Implementation

int n, m;
vector < vector<long long> > dp;


void calc (int x = 0, int y = 0, int mask = 0, int next_mask = 0)
{
    if (x == n)
        return;
    if (y >= m)
        dp[x+1][next_mask] += dp[x][mask];
    else
    {
        int my_mask = 1 << y;
        if (mask & my_mask)
            calc (x, y+1, mask, next_mask);
        else
        {
            calc (x, y+1, mask, next_mask | my_mask);
            if (y+1 < m && ! (mask & my_mask) && ! (mask & (my_mask << 1)))
                calc (x, y+2, mask, next_mask);
        }
    }
}


int main()
{
    cin >> n >> m;

    dp.resize (n+1, vector<long long> (1<<m));
    dp[0][0] = 1;
    for (int x=0; x<n; ++x)
        for (int mask=0; mask<(1<<m); ++mask)
            calc (x, 0, mask, 0);

    cout << dp[n][0];

}

Дасгал бодлогууд

Ашигласан материал