很有趣的一道题目，套了两个动态规划。
Promblem Statement
题目大意是有N个顶点，需要连M条无向边，要求两个顶点A, B的序号满足0 < |A - B| <= K，K<=8，问说一共有多少种方案。
f[i][j][mask][k]表示考虑顶点0...i，使用j条边，前从i往前的K个顶点加上自己的的位状态是mask，并且考虑从i到i - k的连边方案的总方案数。
则f[N - 1][M][0][K]就是答案。
当顶点i处未连出边，则退化成i-1的情况。
否则考虑从i到i-k的连边，
如果不选择边，且i到i-k的连边继承自从i到i-(k-1)的连边，所以直接传递；
如果选择边，则从边少1条的状态中传递。
#include <iostream>using namespace std;const int MOD = 1000000007;typedef long long int64;int64 f[35][1 << 9][35][9];class DengklekBuildingRoads{public:int numWays(int N, int M, int K) { memset(f, 0, sizeof(f));for(int k = 0; k <= K; k++) f[0][0][0][k] = 1;//f[0][0][0][0] = 1; for(int i = 1; i < N; i++) {for(int j = 0; j <= M; j++) {// k = 0 for(int mask = 0; mask < (1 << (K + 1)); mask++) {if(!(mask & 1)) f[i][mask][j][0] = f[i - 1][mask / 2][j][K]; }// k > 0 for(int k = 1; k <= K; k++) {for(int mask = 0; mask < (1 << (K + 1)); mask++) { f[i][mask][j][k] = f[i][mask][j][k - 1];if(k > i) continue; f[i][mask][j][k] += f[i][mask ^ 1 ^ (1 << k)][j - 1][k]; f[i][mask][j][k] %= MOD; } } } }return f[N - 1][0][M][K]; }};转载于:https://www.cnblogs.com/litstrong/archive/2012/02/22/2363433.html
