POJ 3254--Corn Field

2392 단어 POJ동적 기획
제목: 또 farmer john과 그의 소가 M*N의 옥수수밭을 정했다. 어떤 점에는 옥수수가 있고 어떤 점은 없다. 이 소들을 옥수수가 있는 점에 놓고 서로 인접하지 않는 방법이 모두 몇 가지가 있느냐고 물었다. 소의 개수는 0개, 1개와 그림에 인접하지 않는 가장 큰 덩어리를 넣을 수 있다.
문제풀이: 동적 기획.
  • num[i][j]를 1행에서 i행까지 i행의 방치 상태를 j로 하는 총 방법을 설정합니다.j의 2진법은 1행 N열의 소를 대표하는 방법이다.
  • i+1행의 실행 가능한 방법은 i행의 방법과만 관계가 있으며, i행의 상태는oldstate, i+1 상태는 newstate, 상태 이동의 조건은 다음과 같다:
  • new_state가 가능해야 합니다, 즉 newstate의 2진 비트는 인접한 1이 없습니다. (가장 낮은 두 비트가 두 개의 1인지 여부를 이동해서 볼 수 있습니다.)
  • new_state 중 1은 반드시 i+1줄의 비옥한 옥수수밭이어야 한다(new state &fertile [i+1] = = new state).
  • new_state&old_state == 0.
  • 상기 조건을 만족시키면 dp[i+1] [new state] + = dp[i] [old state].

    • 주의: 조건1에서 알 수 있듯이 우리는 가능한 상태를 먼저 열거할 수 있으며 매번 2^N의 상태를 훑어보지 않아도 실제 N=12시에는 377가지 실행 가능한 상태만 있을 뿐이다.
    #include
#include
#include
using namespace std;
#define maxP 100000000

class solve
{
private:
    int M,N;
    int fertile[13];
    int num[13][378];
    int feasibleState[378];
    int stateNum;
public:
    solve(int m,int n):M(m),N(n)
    {
        processIn();
        generateState();
        printf("%d
    ",dp());
    }
    int processIn();
    bool IsFeasible(int state);
    int generateState();
    int dp();
};

int solve::dp()
{
    int i,j,k;
    int oldState,newState;
    memset(num,0,sizeof(num));
    num[0][0] = 1;
    for(i = 1;i <= M;i++)
    {
        for(j = 0;j < stateNum;j++)
        {
            oldState = feasibleState[j];
            for(k = 0;k < stateNum;k++)
            {
                newState = feasibleState[k];
                if((newState&fertile[i]) == newState&&(oldState&newState) == 0)
                {
                    num[i][k] = (num[i-1][j]+num[i][k])%maxP;
                }
            }
        }
    }
    int totNum = 0;
    for(i = 0;i < stateNum;i++)
    {
        totNum = (totNum+num[M][i])%maxP;
    }
    return totNum;
}

bool solve::IsFeasible(int state)
{
    while(state)
    {
        if((state&3) == 3)
            return 0;
        state >>= 1;
    }
    return 1;
}

int solve::generateState()
{
    int i,j;
    stateNum = 0;
    j = 1<
    FastCgi 와 PHP - fpm 관계
    롤링 팬더의 속도를 높입니다.

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage