很有趣的一道题目&＃xff0c;套了两个动态规划。
Promblem Statement
题目大意是有N个顶点&＃xff0c;需要连M条无向边&＃xff0c;要求两个顶点A, B的序号满足0 <|A - B| <&＃61; K&＃xff0c;K<&＃61;8&＃xff0c;问说一共有多少种方案。
f[i][j][mask][k]表示考虑顶点0...i&＃xff0c;使用j条边&＃xff0c;前从i往前的K个顶点加上自己的的位状态是mask&＃xff0c;并且考虑从i到i - k的连边方案的总方案数。
则f[N - 1][M][0][K]就是答案。
当顶点i处未连出边&＃xff0c;则退化成i-1的情况。
否则考虑从i到i-k的连边&＃xff0c;
如果不选择边&＃xff0c;且i到i-k的连边继承自从i到i-(k-1)的连边&＃xff0c;所以直接传递&＃xff1b;
如果选择边&＃xff0c;则从边少1条的状态中传递。
#include
using namespace std;
const int MOD &＃61; 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 &＃61; 0; k <&＃61; K; k&＃43;&＃43;)
f[0][0][0][k] &＃61; 1;
//f[0][0][0][0] &＃61; 1;
for(int i &＃61; 1; i
for(int j &＃61; 0; j <&＃61; M; j&＃43;&＃43;)
{
// k &＃61; 0
for(int mask &＃61; 0; mask <(1 <<(K &＃43; 1)); mask&＃43;&＃43;)
{
if(!(mask & 1)) f[i][mask][j][0] &＃61; f[i - 1][mask / 2][j][K];
}
// k > 0
for(int k &＃61; 1; k <&＃61; K; k&＃43;&＃43;)
{
for(int mask &＃61; 0; mask <(1 <<(K &＃43; 1)); mask&＃43;&＃43;)
{
f[i][mask][j][k] &＃61; f[i][mask][j][k - 1];
if(k > i) continue;
f[i][mask][j][k] &＃43;&＃61; f[i][mask ^ 1 ^ (1 <
f[i][mask][j][k] %&＃61; MOD;
}
}
}
}
return f[N - 1][0][M][K];
}
};
京公网安备 11010802041100号