jzoj1266, P1879-[USACO06NOV] 옥수수밭 Corn Fields[상태압축, dp]

3374 단어 dp기타

본제


평가 레코드:https://www.luogu.org/recordnew/lists?uid=52918&pid=P1879

소홀하다


n*m의 행렬이 있는데, 어떤 곳은 놓을 수 있고, 어떤 곳은 놓을 수 없고, 다른 곳은 놓을 수 없으니, 방치 방법의 총수를 구하세요.

문제풀이의 방향


먼저 이진법으로 각 줄의 방치 가능 상태를 표시한다.그리고state[i]s t a t e[i]로 단행 i종의 상태만 계산하는 것이 합법적인지 여부를 나타낸다.그리고 매번 상태를 왼쪽으로 옮기고 오른쪽으로 옮기면 & 연산으로 합법성을 판단하면 됩니다.그 다음에 우리는 dp로 f[i][j]f[i][j]로 제i행 제j종의 상태를 표시하는 방안수를 시작한다.그리고 우리는 윗줄의 상태 kk를 열거한 다음에 두 상태가 합법적인지 판단한다.

code

#include
#include
#define MN 4100
using namespace std;
int n,m,c,f[MN],F[14][MN],state[MN],ans,MS;
int main()
{
    //freopen("cowfood.in","r",stdin);
    //freopen("cowfood.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
      for (int j=1;j<=m;j++)
      {　
        scanf("%d",&c);
        f[i]=(f[i]<<1)+c;
      }
    MS=1<<m;
    for (int i=0;istate[i]=!(i&(i<<1)||i&(i>>1));
    F[0][0]=1;
    for (int i=1;i<=n;i++)
      for (int j=0;jif (state[j]&&(j&f[i])==j)
          for (int k=0;kif (!(k&j))
              F[i][j]=(F[i][j]+F[i-1][k])%100000000;
    for (int i=0;i%100000000;
    printf("%d",ans);
}
PHP에 대한 빠른 소개
Ruby I18n gem으로 Rails 앱 국제화

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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