ACM模版

描述

题解

虽然一眼就看出来了状压 dp，但是再往后我就不知道从何下手了，有些懵逼，不是太清楚如何转移。找了找官方题解，发现我果然想不到这个，但是我依然无法按照题解的提示写出来，这就尴尬了，好在网上很多大神写过这个博客，我就参考了一下他们的代码，我只想说……

╮(╯▽╰)╭哎，顺便贴一下官方题解吧，毕竟我这么菜，也说不出个一二来~~~

这个预处理完全摸不着头脑，没有见过……

代码

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int MAXN = (1 << 20) + 1;
const int MAXM = 111;

int n, m;
int a[MAXM];
int b[MAXN];
int dp[2][MAXN];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d", a + i);
        a[i]--;
    }

    int tmp = 1 << n;
    for (int i = 0; i <= n; i++)
    {
        b[1 << i] = 1;
    }
    for (int i = 1; i < tmp; i++)
    {
        b[i] = b[i & -i] + b[i ^ (i & -i)];
    }

    int cur = 0, ns;
    memset(dp, -1, sizeof(dp));
    dp[cur][0] = 0;
    for (int i = 0; i < m; i++, cur ^= 1)
    {
        int *last = dp[cur], *now = dp[cur ^ 1];
        for (int s = 0; s < tmp; s++)
        {
            if (last[s] != -1)
            {
                now[s] = max(now[s], last[s]);
                if (~s & (1 << a[i + 1]))
                {
                    ns = s | (1 << a[i + 1]);
                    now[ns] = max(now[ns], last[s] + b[ns >> (a[i + 1] + 1)]);
                }
                last[s] = -1;
            }
        }
    }

    printf("%d\n", dp[cur][tmp - 1]);

    return 0;
}