cf235，D Roman and Numbers（状态压缩dp）引发对dp中几种状态类型的思考

最新推荐文章于 2021-09-03 19:26:06 发布

置顶 guognib

最新推荐文章于 2021-09-03 19:26:06 发布

阅读量1.4k

点赞数 3

分类专栏：动态规划问题总结文章标签： cf dp

本文链接：https://blog.csdn.net/guognib/article/details/21647461

版权

动态规划同时被 2 个专栏收录

32 篇文章

订阅专栏

问题总结

4 篇文章

订阅专栏

由本题思考到dp问题的几种状态类型：

对于数据保存在数组a[n]，求解关于这n个数的相关的最优解或计数问题.

（1）线性dp，每个状态表示为一个下标i（或者说是一个固定起点的区间[0, i]）（可以说是起点固定的区间dp）

（2）区间dp，每个状态表示为一个区间[i, j];（枚举的过程考虑的整个区间的所有组合情况(区间组合的顺序)。）

（3）状态压缩dp（集合上的dp），每个状态表示一个多个元素的集合。（枚举的过程可考虑到集合所有点的全排列情况（点的排列顺序））（与前面不同的是，元素之间没有特定小标的位置要求）

而集合表示的含义，根据具体问题有可有不同的意思。

1）即简单的集合的含义。

2）最优匹配对的问题。每个集合表示集合中所有点所能构成的最有匹配问题。

3）集合的所有元素的全排列情况

tsp问题。每个集合表示的是集合中所有点的全排列之后，得到的路径的最优路径值。

本题。和tsp问题类似。每个集合表示的是集合中所有点的全排列之后，能到的所有数字的取模值。

各种状态的具体含义，根据具体问题有可有不同的意思。

D Roman and Numbers

cf235 div2, D Roman and Numbers（状态压缩dp）

下面几乎是本场cf第一名的解法

本题题意：给定数字n（10e18以内）和m（100以内），数字的各位重新排列后得到的能被m整除的数的个数.

（1）即18个数（0~9）（包含重复的数子），组成的所有排列数字能被m整数的数的个数

共18！种情况，优化是必须的。最后在用的是集合状态表示，每个集合表示的含义是，所有元素的全排列的模的情况，所以状态压缩。

（2）尤其注意判重的方法：保证对于同一个串数，只在其后面添加不重复的数字。！！！

//#pragma warning (disable: 4786)
//#pragma comment (linker, "/STACK:16777216")
//HEAD
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <string>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
//LOOP
#define FE(i, a, b) for(int i = (a); i <= (b); ++i)
#define FD(i, b, a) for(int i = (b); i>= (a); --i)
#define REP(i, N) for(int i = 0; i < (N); ++i)
#define CLR(A,value) memset(A,value,sizeof(A))
#define CPY(a, b) memcpy(a, b, sizeof(a))
#define FC(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
//INPUT
#define RI(n) scanf("%d", &n)
#define RII(n, m) scanf("%d%d", &n, &m)
#define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k)
#define RS(s) scanf("%s", s)
//OUTPUT
#define WI(n) printf("%d\n", n)
#define WS(s) printf("%s\n", s)

typedef long long LL;
const int INF = 1000000007;
const double eps = 1e-10;
const int maxn = 550010;

int n, m;
LL dp[1 << 18][100];
vector<int>a;

int main ()
{
    char s[20];
    cin >> s >> m;
    int n = strlen(s);
    for (int i = 0; i < n; i++) a.push_back(s[i] - '0');
    sort(a.begin(), a.end());///!!!
    int ALL = (1 << n) - 1;
    dp[0][0] = 1;
    for (int r = 0; r <= ALL; r++)
        for (int i = 0; i < m; i++) if (dp[r][i])
        {
            int x = i * 10;///将下个数插到最后!!!
            int pre = -1;
            for (int j = 0; j < n; j++) if (!(r & (1 << j)))
            {
                if ((r == 0 && a[j] == 0) || (a[j] == pre)) continue;///保证首位不为0且不重复!!!
                int nowx = (x + a[j]) % m;
                pre = a[j];
                dp[r | (1 << j)][nowx] += dp[r][i];
//                cout << nowx << ' ' << dp[r][i] << ' ' << dp[r | (1 << j)][nowx] << endl;
            }
        }
    cout << dp[ALL][0] << endl;
    return 0;
}


/**
（1）重复的问题
（2）与背包的结合
（3）0-1和完全的区别
*/