loj#10172 涂抹果酱 (状压DP)
2019-10-12 08:09:58来源:博客园 阅读 ()
loj#10172 涂抹果酱 (状压DP)
题目:
#10172. 「一本通 5.4 练习 1」涂抹果酱
解析:
三进制的状压DP
经过简单的打表发现,在\(m=5\)时最多有\(48\)种合法状态
然后就向二进制一样枚举当前状态和上一层的状态进行转移就好了
由于第\(k\)行是给定的,所以转移时要特判一下第\(k\)行,并且注意下一\(k=1\)的情况
设\(f[i][j]\)表示第\(i\)行\(j\)状态时的方案数
\(f[i][j] += f[i - 1][k],k是上一行的状态\)
代码:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
const int mod = 1e6;
int n, m, k, num, sum = 1, sta, kk, ans;
/*
sum为状态上节
sta是第k行状态
num是合法状态数
*/
int state[N], f[10010][50];
//state记录状态
//f[i][j]表示dp 到第i行j状态的方案数
bool check(int x) { //判断状态是否合法
int len = 0;
int b[10];
while (x) b[++len] = x % 3, x /= 3;
if (len < m - 1) return 0;
for (int i = 2; i <= len; ++i) if (b[i] == b[i - 1]) return 0;
return 1;
}
bool cmp(int x, int y) { //判断两个状态是否可以相邻
for (int i = 1; i <= m; ++i) {
if ((x % 3) == (y % 3)) return 0;
x /= 3, y /= 3;
}
return 1;
}
signed main() {
cin >> n >> m >> k;
for (int i = 1, x; i <= m; ++i) cin >> x, kk = kk * 3 + x - 1;
for (int i = 1; i <= m; ++i) sum *= 3;
for (int i = 0; i < sum; ++i) if (check(i)) {
state[++num] = i;
if (i == kk) sta = num;
}
if (sta == 0) {
cout << 0;
return 0;
}
for (int i = 1; i <= n; ++i) {
if (i == k) {
if (i == 1) f[1][sta] = 1;
else for (int j = 1; j <= num; ++j)
if (cmp(state[sta], state[j]))
(f[i][sta] += f[i - 1][j]) %= mod;
} else {
if (i == 1) for (int j = 1; j <= num; ++j) f[i][j] = 1;
else for (int j = 1; j <= num; ++j)
for (int pre = 1; pre <= num; ++pre)
if (cmp(state[j], state[pre]))
(f[i][j] += f[i - 1][pre]) %= mod;
}
}
for (int i = 1; i <= num; ++i) (ans += f[n][i]) %= mod;
cout << ans;
}
原文链接:https://www.cnblogs.com/lykkk/p/11650244.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash