bzoj1725 [USACO 2006 NOV] Corn Fields 목장의 안배(상압 dp)

2874 단어 bzoj상압
저번 문제 비슷한데...이 문제는 n=12로 줄마다 상태가 다르기 때문에 우리는 미리 처리하지 않겠습니다.dp[i][k]는 i행의 상태가 k라는 합법적인 방안을 나타낸다. i-1행의 상태가 j이고 j이며 k는 인접행의 방안 수와 같다.
#include
#define mod 1000000000
int n,m,dp[13][4096],mp[13],ans=0;
int main(){
//  freopen("a.in","r",stdin);
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;++i)
        for(int j=0;jint x;scanf("%d",&x);
            if(x) mp[i]+=x<int end=(1<1;
    for(int i=0;i<=end;++i)
        if((i&(i>>1))==0&&(i|mp[1])==mp[1]) dp[1][i]=1;
    for(int i=2;i<=m;++i)
        for(int j=0;j<=end;++j)
            if(dp[i-1][j])
                for(int k=0;k<=end;++k)
                    if((k&j)==0&&(k|mp[i])==mp[i]&&(k&k>>1)==0) 
                        dp[i][k]=(dp[i][k]+dp[i-1][j])%mod;
    for(int i=0;i<=end;++i) ans=(ans+dp[m][i])%mod;
    printf("%d
",ans);
    return 0;
}
LetCode 매일 퀴즈 542.01 Matrix
XDU-1107 Too Simple (DP)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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