欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

loj#10172 涂抹果酱 (状压DP)

程序员文章站 2022-05-26 13:06:25
题目: " 10172. 「一本通 5.4 练习 1」涂抹果酱" 解析: 三进制的状压DP 经过简单的打表发现,在m=5时最多有48种合法状态 然后就向二进制一样枚举当前状态和上一层的状态进行转移就好了 由于第k行是给定的,所以转移时要特判一下第k行,并且注意下一k=1的情况 代码: cpp inc ......

题目:

解析:

三进制的状压dp
经过简单的打表发现,在m=5时最多有48种合法状态
然后就向二进制一样枚举当前状态和上一层的状态进行转移就好了
由于第k行是给定的,所以转移时要特判一下第k行,并且注意下一k=1的情况

代码:

#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;
}