首页 > 代码库 > poj3254：基础状压dp

poj3254：基础状压dp

2024-07-26 07:17:09   220人阅读

第二个状压dp

做过的第一个也是放牛问题，两头牛不能相邻

这个题多了一个限制，就是有些位置不能放牛

于是先与处理一下每一行所有不能放牛的状态，处理的过程直接对每一个不能放牛的状态或以下

ac代码：

#include <iostream>#include <stdio.h>#include<string.h>#include<algorithm>#include<string>#include<ctype.h>using namespace std;#define mod  100000000int dp[15][4100];int cant[15];int n,m;void ini(){    memset(cant,0,sizeof(cant));    int x;    for(int i=0;i<n;i++)    {        for(int j=0;j<m;j++)        {            scanf("%d",&x);            if(x==0)            {                cant[i]|=(1<<j);            }        }    }}void solve(){    memset(dp,0,sizeof(dp));    for(int i=0;i<1<<m;i++)    {        if(cant[0]&i)            continue;        if(i&(i<<1))        {            dp[0][i]=0;        }        else        {            dp[0][i]=1;        }    }    for(int i=1;i<n;i++)    {        for(int j=0;j<1<<m;j++)        {            if(j&cant[i])                continue;            if(j&(j<<1))                continue;            for(int k=0;k<1<<m;k++)            {                if(j&k)                    continue;                dp[i][j]=(dp[i-1][k]+dp[i][j])%mod;            }        }    }    int ans=0;    for(int i=0;i<1<<m;i++)    {        ans=(ans+dp[n-1][i])%mod;    }    printf("%d\n",ans);}int main(){    while(scanf("%d%d",&n,&m)!=EOF)    {        ini();        solve();    }    return 0;}

 

poj3254：基础状压dp


联系
我们