hdu 1693 Eat the Trees——插头DP

题目:http://acm.hdu.edu.cn/showproblem.php?pid=1693

第一道插头 DP !

直接用二进制数表示状态即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=,M=(<<)+;
int n,m,bin[N];ll dp[N][N][M];
int b[N][N];
void solve()
{
int lm=m+;
bin[]=;for(int i=;i<=lm;i++)bin[i]=bin[i-]<<;
memset(dp,,sizeof dp); dp[][][]=;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
for(int s=;s<bin[lm];s++)
{
if(!dp[i][j][s])continue;
ll tp=dp[i][j][s];bool d0=s&bin[j-],d1=s&bin[j];
// ll tp not int tp!!!!!
if(!b[i][j])
{
if(!d0&&!d1)dp[i][j+][s]+=tp;
continue;
}
int t=s^bin[j-]^bin[j];
if((d0&&d1)||(!d0&&!d1))
dp[i][j+][t]+=tp;
if((d0&&!d1)||(!d0&&d1))
dp[i][j+][s]+=tp, dp[i][j+][t]+=tp;
}
for(int s=;s<bin[lm];s++)
{
if(!dp[i][lm][s]||s&bin[m])continue;
dp[i+][][s<<]+=dp[i][lm][s];
}
}
}
int main()
{
int T; scanf("%d",&T);
for(int t=;t<=T;t++)
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&b[i][j]);
solve();
printf("Case %d: There are %lld ways to eat the trees.\n",
t,dp[n][m+][]);
}
return ;
}
上一篇:运动、下厨和看电影的闲暇时光


下一篇:GDI+ 读取jpg图片每个像素的值