状态压缩DP 洛谷P1896

//MADE BY Y_is_sunshine;
//#include <bits/stdc++.h>
//#include <memory.h>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define INF 0x3f3f3f3f
#define MAXN 1024

const int mod = 1e9 + 7;
const double PI = acos(-1);

using namespace std;

int king[MAXN];
int state[MAXN];
long long dp[15][1024][105];

int N, M;
int cnt;

void init(void) {
    int tot = (1 << N) - 1;
    for (int i = 0; i <= tot; i++) {
        if (!((i << 1) & i)) {
            state[++cnt] = i;
            int temp = i;
            while (temp) {
                king[cnt] += temp & 1;
                temp >>= 1;
            }
        }
    }
}

int main(void)
{
    freopen("data.txt", "r", stdin);

    ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    cin.tie(NULL);

    cin >> N >> M;

    init();
    for (int i = 1; i <= cnt; i++)
        if (king[i] <= M)
            dp[1][i][king[i]] = 1;

    for (int i = 2; i <= N; i++) {
        for (int j = 1; j <= cnt; j++) {
            for (int k = 1; k <= cnt; k++) {
                if (state[j] & state[k]) continue;
                if ((state[j] << 1) & state[k]) continue;
                if (state[j] & (state[k] << 1)) continue;
                for (int o = max(1, king[j]); o + king[k] <= M; o++) {
                    dp[i][k][o + king[k]] += dp[i - 1][j][o];
                }
            }
        }
    }

    long long ans = 0;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= cnt; j++)
            ans += dp[i][j][M];
    cout << ans << endl;

    freopen("CON", "r", stdin);
    system("pause");
    return 0;
}

//MADE BY Y_is_sunshine;
//#include <bits/stdc++.h>
//#include <memory.h>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define INF 0x3f3f3f3f
#define MAXN 1024

const int mod = 1e9 + 7;
const double PI = acos(-1);

using namespace std;

int king[MAXN];
int state[MAXN];
long long dp[15][1024][105];

int N, M;
int cnt;

void init(void) {
	int tot = (1 << N) - 1;
	for (int i = 0; i <= tot; i++) {
		if (!((i << 1) & i)) {
			state[++cnt] = i;
			int temp = i;
			while (temp) {
				king[cnt] += temp & 1;
				temp >>= 1;
			}
		}
	}
}

int main(void)
{
	freopen("data.txt", "r", stdin);

	ios::sync_with_stdio(false);
	//cin.tie(nullptr);
	cin.tie(NULL);

	cin >> N >> M;

	init();
	for (int i = 1; i <= cnt; i++)
		if (king[i] <= M)
			dp[1][i][king[i]] = 1;

	for (int i = 2; i <= N; i++) {
		for (int j = 1; j <= cnt; j++) {
			for (int k = 1; k <= cnt; k++) {
				if (state[j] & state[k]) continue;
				if ((state[j] << 1) & state[k]) continue;
				if (state[j] & (state[k] << 1)) continue;
				/*for (int o = max(1, king[j]); o + king[k] <= M; o++) {
					dp[i][k][o + king[k]] += dp[i - 1][j][o];
				}*/
				for (int o = king[j]; o + king[k] <= M; o++) {
					dp[i][k][o + king[k]] += dp[i - 1][j][o];
				}
			}
		}
	}

	long long ans = 0;
	/*for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= cnt; j++) {
			for (int k = 0; k <= M; k++)
				cout << dp[i][j][k] << "  ";
			putchar(10);
		}
		putchar(10);
	}*/
	for (int i = 1; i <= cnt; i++)
		ans += dp[N][i][M];
	cout << ans << endl;

			

	freopen("CON", "r", stdin);
	system("pause");
	return 0;
}

两种写法 第一种没有转移0这种情况 第二种转移0
[洛谷P](https://www.luogu.org/problem/P1896)