HDU 5779 BestCoder Round #85 Tower Defence ( dp升级版 )

HDU 5779 BestCoder Round #85 Tower Defence ( dp升级版 )

Tower Defence

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 85    Accepted Submission(s): 50

Problem Description

Little White recently likes playing Tower Defence. She wants to make a map. The map is an undirected graph which has n vertices(graph may not connect).The length of each edge is 1.The shortest distance of vertice 1 to any other vertices is not equal to k.She wants to know how many graphs which satisfy all these conditions.If two vertices is disconnected, the distance between them is infinite.

Input

The first line of input is an integer T（1≤T≤10) For each test case the first line contains two integers n and k(1≤k，n≤60)

Output

For each testcase , output a line, the answer mod 1，000，000，007

Sample Input

3 3 2 4 2 5 3

Sample Output

6 28 808

Source

​​BestCoder Round #85​​

Recommend

wange2014   |   We have carefully selected several similar problems for you:  ​​5775​​​ ​​5774​​​ ​​5773​​​ ​​5772​​​ ​​5771​​

题意：小白最近痴迷于玩Tower Defence。他想要自己制作一张地图。地图是一张有n个点的无向图（图可以不连通,没有重边和自环），所有边的长度都为1，满足从1号点到其他任意一个点的最短路都 不等于 k.小白想知道这样的图有多少个。如果两个顶点不连通，则它们之间的距离为无穷大。

官方题解：

首先最短路不等于k，可以转化成最短路小于k 考虑dp[i][d][j]表示连通块大小为 i，最短路长度为 d，恰好离1距离为d的有j个转移枚举最短路长度为d-1的有k个，那么首先长度为d的只能向长度为d-1的连边，至少连1条，最多连k条的方案，接着考虑距离为d的j个点，内部连的方案，最后考虑i-1个点中选j个点的方案（因为1号点离自己距离为0）。求出dp[i][d][j]后，对答案的贡献为从n-1个点中选i-1个点组成连通块大小为i的方案（因为1号点一定在连通块内），乘上剩下n-i个点内部乱连的方案。复杂度O(n^3*k) 。

（比1005还难很多。。。）

AC代码：

#includeusing namespace std;typedef long long LL;const int N=65;const int mod=1000000007;int dp[N][N][N];int p2[N*N];int pp[N][N];int C[N][N];void init(){ for(int i=0; i < N ; i++) { C[i][i] = C[i][0] = 1; for(int j = 1 ; j < i; j++) { C[i][j] = ( C[i-1][j-1] + C[i-1][j] )%mod; } } p2[0] = 1; for(int i = 1; i < N*N; i++) p2[i] = p2[i-1] * 2 % mod; for(int i = 0; i < N; i++) { pp[i][0] =1; for(int j = 1; j < N; j++) { pp[i][j]= 1LL * pp[i][j-1] * ( p2[i]-1 ) % mod; } } dp[1][1][1] = 1; for(int i = 2; i < N; i++){ for(int j = i; j < N; j++){ for(int k = 1; k < j; k++) { for(int u=1; u+k <= j; u++) { dp[i][j][k] +=1LL*dp[i-1][j-k][u] *pp[u][k] % mod*p2[k*(k-1)/2] %mod * C[j-1][k]%mod; if(dp[i][j][k] >= mod) dp[i][j][k]-=mod; } } } }}int main(){ init(); int n,k; int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&k); int ans=0; for(int i = 1; i<=k; i++) { for(int d = 1; d <= n; d++) { for(int j = 1; j <= d; j++) { ans+= 1LL*dp[i][d][j]*C[n-1][d-1] % mod * p2[(n-d)*(n-d-1)/2] % mod; if(ans >= mod) ans -= mod; } } } printf("%d\n",ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。