[Usaco 2006 Nov] Corn Fields 목장의 배치 장압 DP

첫눈에 보니까 장압DP.
그리고 삼진 매거자집으로 하자.
이 문제는 정말 입문하기 좋은 문제다...
dp[i][j]는 i행을 나타내고 j상태에서 전 i행의 분배 방안 수를 나타낸다.
그럼 dp[i][j]는 i-1 줄에서 돌렸을 거예요.
그러면 붙어 있을 수 없기 때문에 우리는 i-1행 상태를 매거할 때 j의 누구도 포함할 수 없다.
그러면 k=(1<이렇게 k를 매거하는 서브집합입니다.
int sub = k;
do
{
sub = k& (sub - 1);
}while(sub != k);
그리고 각 자집에 대해 합법성을 판단한 다음에 더하면 된다.

#include 
#include 
#include 
#include 
#include 
#define MAXN 1005
#define INF 1000000000
using namespace std;
int dp[13][1 << 13];
int n, m;
int st[13];
int mod = 100000000;
bool ok(int s, int pos)
{
    if((s | st[pos]) > st[pos]) return false;
    for(int i = 0; i < n; i++)
        if(s & (1 << i))
        {
            if(s & (1 << (i + 1))) return false;
        }
    return true;
}
int main()
{
    int x;
    scanf("%d%d", &m, &n);
    for(int i = 1; i <= m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            scanf("%d", &x);
            if(x) st[i] |= (1 << j);
        }
    }
    dp[0][0] = 1;
    for(int i = 1; i <= m; i++)
    {
        for(int k = 0; k < (1 << n); k++)
        {
            int s = ((1 << n) - 1) ^ k;
            if(ok(k, i))
            {
                //printf("%d %d
", k, s);
                dp[i][k] += dp[i - 1][0];
                for(int j = s; j; j = s & (j - 1))
                {
                    if(ok(j, i - 1))
                    dp[i][k] = (dp[i][k] + dp[i - 1][j]) % mod;
                }
            }
        }
    }
    int ans = 0;
    for(int i = 0; i < (1 << n); i++)
        ans = (ans + dp[m][i]) % mod;
    printf("%d
", ans);
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[USACO] 2021 December - Bronze

N\le500,000 O(N \log N) O(N^2) O(N2)이라 포기. O(N) O(N) 풀이다. O(N^2) O(N2) 아닌가? O(N) O(N). O(NT) N \le 100,000 O(NT) O(N) O(...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

[Usaco 2006 Nov] Corn Fields 목장의 배치 장압 DP

좋은 웹페이지 즐겨찾기