1211. 商人的宣传

TAG 动态规划 矩阵乘法

题目的意思讲得不是很清楚。起点是不算第一天的，路途不算时间，而且要刚好在第L天到达目的地，不能提前到达。。

如果一个矩阵M代表邻接矩阵，M的n次幂 M^n 便是经过n步能到达的路径数。用原始方法时间复杂度为O(n)*O(m^3 )因为我没想到log(n)次的矩阵算法，所以用了动态规划做。O(L*n^2)，结果排在Status的第一页 (‖▔ ω▔)

转移方程

dp[i][j]表示走i步到达j时的路径数

dp[i][j]=∑dp[i-1][x] if map[x][j]==1

用矩阵方法的参见http://fghtech.blogbus.com/logs/64953452.html

#include <stdio.h>
#include <memory.h>
const int N=100;
int  g[N][N];
int  dp[N][N];
int  n,m,l;
int  a,b,q,s,t;
int  ans;
void cal()
{
	memset(dp, 0, sizeof(dp) );
	for (int i=1; i<=g[s][0]; ++i)
	{
		dp[0][ g[s][i] ]=1;
	}
	
	for (int v=2; v<=l; ++v)
	{
		for (int i=0; i<n; ++i)
		{
			for (int j=1; j<=g[i][0]; ++j)
			{
				dp[v-1][ g[i][j] ]+=dp[v-2][i];
			}
		}
	}
	ans=dp[l-1][t];
}
int main(int argc, char *argv[])
{
	while (	scanf("%d%d%d", &n, &m, &l)!=EOF )
	{
				memset(g, 0, sizeof(g) );
		for (int i=0; i<m; ++i)
		{
			scanf("%d%d", &a, &b);
			--a;
			--b;
			++g[a][0];
			g[a][ g[a][0] ]=b;
		}
		scanf("%d", &q);
		while ( q-- )
		{	
			scanf("%d%d", &s, &t);
			--s;
			--t;
			cal();
			printf("%d/n", ans);		
		}
	}
	return 0;
}