首页 > 其他分享 >327. 玉米田

327. 玉米田

时间:2024-07-05 11:20:24浏览次数:14  
标签:12 种植 玉米田 土地 int 327

// 327. 玉米田.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

using namespace std;


/*
https://www.acwing.com/problem/content/329/

农夫约翰的土地由 M×N 个小方格组成,现在他要在土地里种植玉米。

非常遗憾,部分土地是不育的,无法种植。

而且,相邻的土地不能同时种植玉米,也就是说种植玉米的所有方格之间都不会有公共边缘。

现在给定土地的大小,请你求出共有多少种种植方法。

土地上什么都不种也算一种方法。

输入格式
第 1 行包含两个整数 M 和 N。

第 2..M+1 行:每行包含 N 个整数 0 或 1,用来描述整个土地的状况,1 表示该块土地肥沃,0 表示该块土地不育。

输出格式
输出总种植方法对 108 取模后的值。

数据范围
1≤M,N≤12
输入样例:
2 3
1 1 1
0 1 0
输出样例:
9
*/
const int N = 12;
long long dp[N+5][1<<N];
int f[N+5];
int n, m;
const int MOD = 1e8;


bool check(int a, int b) {
	if ( (a & b) != 0) return false;
	return true;
}

bool rule(int x) {
	int state = 0;
	while (x != 0) {
		if (x & 1 && state == 1) return false;
		state = x & 1;
		x >>= 1;
	}

	return true;
}



int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		int t = 0;
		for (int j = 0; j < m; j++) {
			int a; cin >> a;
			if (a == 0) t += 1 << j;
		}
		f[i] = t;
	}

	dp[0][0] = 1;

	for (int i = 1; i <= n+1; i++) {
		for (int prev = 0; prev < 1 << m; prev++) {
			if (rule(prev) == false) continue;
			for (int curr = 0; curr < 1 << m; curr++) {
				if (rule(curr) == false) continue;
				if (check(prev, curr) && check(curr, f[i])) {
					dp[i][curr] += dp[i - 1][prev];
					dp[i][curr] %= MOD;
				}
			}
		}
	}
	long long ans = 0;
	for (int curr = 0; curr < 1 << m; curr++) {
		ans += dp[n][curr];
		ans %= MOD;
	}
	cout << ans << endl;


	return 0;
}

标签:12,种植,玉米田,土地,int,327
From: https://www.cnblogs.com/itdef/p/18285435

相关文章

  • 计算机毕业设计项目推荐,32762 外卖app系统设计与实现(开题答辩+程序定制+全套文案 )上万
    摘 要随着科学技术的飞速发展,社会的方方面面、各行各业都在努力与现代的先进技术接轨,通过科技手段来提高自身的优势,餐饮外卖当然也不例外。外卖app系统主要功能模块包括后台首页,轮播图,资源管理(餐饮新闻,新闻分类),系统用户(注册用户,配送员,注册商家)模块管理(美食信息,外卖点餐,配......
  • P9327 [CCC 2023 S4] Minimum Cost Roads
    原题链接题解贪心,我管这种叫做策略贪心,即按照某种顺序或者角度去贪心可以得到最优解既然题目要求任意两点间最短路最小的同时,价格也最小,那么我们就按长度为第一关键字,花费为第二关键字排序。然后遍历所有边看看这条边能否使用遍历过程的策略:如果这条边加入后,这条边两端的节点......
  • P3270 [JLOI2016] 成绩比较
    记\(a_i=N-R_i,n=N-1\)。先不考虑有多少人被碾压,计算出符合排名限制的方案数。枚举每门课和B神在每门课中的得分,选出\(a_i\)个人得分小于等于他,即:\[\prod\limits_{i=1}^m\dbinom{n}{a_i}\sum\limits_{j=1}^{U_i}j^{a_i}(U_i-j)^{n-a_i}\]设\(s(x)=\sum\limits_{j=1}^{......
  • P5327 [ZJOI2019]语言 解题报告
    oj:https://gxyzoj.com/d/gxyznoi/p/P35树上差分+线段树合并+树链剖分1.暴力从最基础的方法开始,暴力统计s-t上的点,然后用map直接统计,显然会T,20pts2.特殊性质测试点5,6保证了数据是一条链,将链上每一个节点编号为1-n对于每一次操作,可以记录其覆盖情况,设共有x个节点,有y个节......
  • SIT327网络取证学习 - 1
    WiFi取证分析背景学习:对于大型数据包捕获,tcpdump和tshark相比较于Wireshark来说更加有效与更具有可扩展性。802.11是一组不断发展的无线局域网(wlan)规范,由IEEE电气和电子工程师协会的一个工作组开发和维护。802.11是第一个被广泛采用的无线网络标准。802.11是原始的无线规......
  • 20240327
    T1洛谷P2047社交网络暴力Floyd跑出每两个点间最短路及其条数,然后暴力枚举算。代码#include<iostream>#include<string.h>#include<iomanip>#include<queue>#defineintlonglongusingnamespacestd;intn,m;intdist[105][105];intcnt[105][105];sign......
  • 20240327打卡
    第五周第一天第二天第三天第四天第五天第六天第七天所花时间20h4h4h代码量(行)877164371博客量(篇)111知识点了解navigation路由配置,jetpackcompose组件运用,容器封装第一次结对作业开始Web搓后端ing~主要完成了用户登录与管......
  • 20240327每日一题题解
    20240327每日一题题解Problem一些整数可能拥有以下的性质:性质1:是偶数;性质2:大于\(4\)且不大于\(12\)。小A喜欢这两个性质同时成立的整数;Uim喜欢这至少符合其中一种性质的整数;小B喜欢刚好有符合其中一个性质的整数;正妹喜欢不符合这两个性质的整数。现在给出一个......
  • P3327 [SDOI2015] 约数个数和
    题意求:\[\sum_{i=1}^n\sum_{j=1}^md(ij)\]其中\(d(n)\)代表\(n\)的约数个数。Sol考虑拆开\(d(ij)\),平凡的想法是考虑\(i\)和\(j\)分别对\(d(ij)\)提供因子。注意到若\(i\)能提供完因子\(p\),那么直接从\(i\)里取即可。否则需要在\(j\)里取因子......
  • Programming Abstractions in C阅读笔记:p327-p330
    《ProgrammingAbstractionsinC》学习第78天,p327-p330,总计4页。一、技术总结1.ADT(抽象数据类型)p328,Atypedefinedintermofitsbehaviorratherthanitsrepresnetationiscalledanabstractdatatype(如果一种数据类型使用它们的行为而不是表示来定义,那么这样的......