首页 > ACM题库 > HDU-杭电 > hdu 1978 How many ways-动态规划-[解题报告]C++
2013
12-26

hdu 1978 How many ways-动态规划-[解题报告]C++

How many ways

问题描述 :

这是一个简单的生存游戏,你控制一个机器人从一个棋盘的起始点(1,1)走到棋盘的终点(n,m)。游戏的规则描述如下:
1.机器人一开始在棋盘的起始点并有起始点所标有的能量。
2.机器人只能向右或者向下走,并且每走一步消耗一单位能量。
3.机器人不能在原地停留。
4.当机器人选择了一条可行路径后,当他走到这条路径的终点时,他将只有终点所标记的能量。

如上图,机器人一开始在(1,1)点,并拥有4单位能量,蓝色方块表示他所能到达的点,如果他在这次路径选择中选择的终点是(2,4)

点,当他到达(2,4)点时将拥有1单位的能量,并开始下一次路径选择,直到到达(6,6)点。
我们的问题是机器人有多少种方式从起点走到终点。这可能是一个很大的数,输出的结果对10000取模。

输入:

第一行输入一个整数T,表示数据的组数。
对于每一组数据第一行输入两个整数n,m(1 <= n,m <= 100)。表示棋盘的大小。接下来输入n行,每行m个整数e(0 <= e < 20)。

输出:

第一行输入一个整数T,表示数据的组数。
对于每一组数据第一行输入两个整数n,m(1 <= n,m <= 100)。表示棋盘的大小。接下来输入n行,每行m个整数e(0 <= e < 20)。

样例输入:

1
6 6
4 5 6 6 4 3
2 2 3 1 7 2
1 1 4 6 2 7
5 8 4 3 9 5
7 6 6 2 1 5
3 1 1 3 7 2

样例输出:

3948

/*
分析:
    简单DP。

flag[][]表示可以到达改点的方法数。

刚开始:
外循环扫描所有点flag[x][y],而内循环扫描出所有可以到达
点x、y的点i、l。
那么flag[x][y]就是所有的flag[i][l]之和。

写的时候就感觉会超时,还真超了- -I。原因很简单么,因为对于
每个x、y点,都要把所有的i<x&&l<y的点都扫描一遍,而好多情况根本
就不用扫描的,因为0<=e<=20;再说况且对于100*100的二维表格,数据
量会很大。
所以,应该将扫描的方式变一下:
外循环扫描所有的[i][l]点,并将flag[i][l]加到[i][l]可达
的点的flag上即可。

    不过我的方法优化后也是187MS,谁有更好的方法欢迎讨论O(∩_∩)O哈!
                                                    2012-04-24
*/

#include"stdio.h"
#include"string.h"
int main()
{
	int flag[111][111];    //方法数。
	int num[111][111];
	int T;
	int n,m;
	int i,l;
	int x,y;


	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		for(i=0;i<n;i++)
			for(l=0;l<m;l++)
				scanf("%d",&num[i][l]);


		memset(flag,0,sizeof(flag));
		flag[0][0]=1;


		for(i=0;i<n;i++)
		{
			for(l=0;l<m;l++)
			{
				if(i==n-1&&l==m-1)	continue;
				flag[i][l]%=10000;
				for(x=i;x<=num[i][l]+i&&x<n;x++)
				{
					for(y=l;y<=num[i][l]+l&&y<m;y++)
					{
						if(x==i&&y==l)	continue;
						if(num[i][l]>=x-i+y-l)
						{
							flag[x][y]+=flag[i][l];
//优化,把这行换个地儿。	flag[x][y]%=10000;    优化前203MS,优化后187MS。
						}
					}
				}
			}
		}
		flag[n-1][m-1]%=10000;


		printf("%d\n",flag[n-1][m-1]);
	}
	return 0;
}

解题转自:http://blog.csdn.net/ice_crazy/article/details/7493940


  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。