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