POJ 3254 简单状压DP
简单 DP poj 状压
2023-09-11 14:14:42 时间
没什么可说的,入门级状压DP。直接撸掉
#include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <algorithm> #include <cmath> #include <vector> #include <map> #include <queue> #include <stack> #include <set> #define LL long long #define FOR(i, x, y) for(int i=x;i<=y;i++) using namespace std; const int maxn = 5000; const int MOD = 100000000; int N, M, K; int C[20], state[maxn]; int dp[20][maxn]; bool judge(int x) { if(x & (x << 1)) return false; return true; } void init() { memset(dp, 0, sizeof(dp)); memset(state, 0, sizeof(state)); memset(C, 0, sizeof(C)); int r = (1 << M) - 1; K = 0; FOR(i, 0, r) if(judge(i)) state[++K] = i; } int main() { while(scanf("%d %d", &N, &M)!=EOF) { init(); int X; FOR(i, 1, N) FOR(j, 1, M) { scanf("%d", &X); if(X == 0) C[i] = C[i] | (1 << (M - j)); } FOR(i, 1, K) { if(!(state[i] & C[1])) dp[1][i] = 1; } FOR(i, 2, N) FOR(j, 1, K) { if(C[i-1] & state[j]) continue; FOR(l, 1, K) { if((C[i] & state[l]) || (state[l] & state[j])) continue; dp[i][l] = (dp[i-1][j] + dp[i][l]) % MOD; } } int ans = 0; FOR(i, 1, K) ans = (ans + dp[N][i]) % MOD; printf("%d\n", ans); } return 0; }
相关文章
- hdu2067 简单dp或者记忆化搜索
- C# 委托和事件,简单示例说明问题
- 蒟蒻关于斜率优化DP简单的总结
- 【简单DP】Kuangbin 免费馅饼
- window下nginx负载均衡简单配置-----权重的实现
- esp32系列(3):GPIO信号传输(以简单GPIO输入输出、ADC、DAC为例)
- HDU 1207 汉诺塔II (简单DP)
- UVa 111 History Grading (简单DP,LIS或LCS)
- node简单入门
- spring boot 多模块简单示例
- 一个简单的例子
- 使用socket编程实现一个简单的文件服务器
- W3af简单使用教程
- URAL 1577. E-mail(简单二维dp)
- EasyUI入门:怎样引入及简单使用
- spring boot 2 + shiro 实现简单的身份验证例子
- JavaScript经典实例之分页(简单易用)原生js封装分页(一次性数据)
- 原来博客中嵌入时频是如此简单
- 基于图像原始像素信息的简单CT/MRI医学图像配准方法
- uni-app 中图片转 base64 以及 base64 转图片方式,超简单,超好用的图片转换工具,你值得拥有它。