CF1391D-505 (思维结论 + 暴力 + 状压dp)
2021/8/25 23:06:51
本文主要是介绍CF1391D-505 (思维结论 + 暴力 + 状压dp),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目要求每一个长度为偶数的正方形里,1的个数都是奇数。
于是我们发现,一旦n >= 4同时 m >= 4那么一定是-1,奇+奇+奇+奇=偶
之后就剩下了三种可能性,n=1,n=2,n=3
于是考虑状压dp。
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int inf = 0x3f3f3f3f; ///1061109567 const int maxn = 1e6 + 10; int n, m; int all; int f[maxn][10]; vector<string> s; ///计算当前当前列到state状态需要的花费 int cal(int p, int state) { bitset<3> bt(state); int cnt = 0; for (int i = 0; i < n; ++ i) { if (bt[i] != s[i][p]-'0') cnt ++; } return cnt; } ///判断是否可以由st1转移到st2(判断合起来是否都是奇数1 bool check(int st1, int st2) { for (int i = 1; i < n; ++ i) { int cnt = ((st1>>i)&1) +((st1>>(i-1))&1) + ((st2>>i)&1) +((st2>>(i-1))&1); if (cnt % 2 == 0) return 0; } return 1; } ///在前面所有可以转移的状态里面取小 int premin(int j, int state) { int minn = 1e9; for (int pre = 0; pre < all; ++ pre) { if (check(pre, state)) minn = min(minn, f[j-1][pre]); } return minn; } int getans(int n) { if (n >= 4) return -1; ///性质 if (n == 1) return 0; all = 1 << n; ///初始化 for (int i = 0; i < all; ++ i) { f[0][i] = cal(0, i); } ///dp for (int j = 1; j < m; ++ j) { for (int i = 0; i < all; ++ i) { f[j][i] = premin(j, i) + cal(j, i); } } int ans = 1e9; for (int i = 0; i < all; ++ i) ans = min(ans, f[m-1][i]); return ans; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++ i) { string t; cin >> t; s.push_back(t); } cout << getans(n) << endl; return 0; }
这篇关于CF1391D-505 (思维结论 + 暴力 + 状压dp)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain