首页 > 其他 > 详细

BZOJ1725 牧场的安排

时间:2019-09-05 18:32:59      阅读:94      评论:0      收藏:0      [点我收藏+]

题目

分析

  讲题快luo!(逃

  2019.9.5 17:00 本人现场表演什么叫蔡讲题,欢迎拍砖。:)

  暂时不开放PPt下载。

  总之用dp[i][j]来表示对于前i行中,第i行采用第j种状态时可以得到的可行方案总数。

  dp[i][j]=dp[i-1][k1]+dp[i-1][k2]++dp[i-1][kn]kn即为上一行可行方案的编号,上一行共有n种可行方案)

  ans=dp[m][k1]+dp[m][k2]++dp[m][kn]kn为最后一行可行方案的编号)

代码

#include<bits/stdc++.h>
using namespace std;
#define Mod 100000000
int n,m,tot,ans;//v[i]//第i行整行的情况
int dp[20][500],s[500],v[20];//dp对于前i行,每行有前j种可能状态时的解
//s[i]存储每行所有可行的状态
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<(1<<m);i++) if((i&(i<<1))==0) s[++tot]=i;//记录不相邻的状态
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			int a;
			scanf("%d",&a);//读入该地块是否可放 
			if(a==0) v[i]+=1<<j-1;//整行的二进制
		}
	}
	dp[0][1]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=tot;j++)//判断第i行假如按方案j放的话行不行
		{
			if(s[j]&v[i]) continue;//判断上一行与其状态是否满足
			for(int k=1;k<=tot;k++)
			{
				if(s[j]&s[k]) continue;
				dp[i][j]=(dp[i][j]+dp[i-1][k])%Mod;
			}
		}
	}
	for(int i=1;i<=tot;i++)
	{
		if(s[i]&v[n]) continue;
		ans=(ans+dp[n][i])%Mod;
	}
	printf("%d",ans);
	return 0;
}

BZOJ1725 牧场的安排

原文:https://www.cnblogs.com/DARTH-VADER-EMPIRE/p/11468692.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!