首页 > ACM题库 > HDU-杭电 > HDU 1876 机器人系列2-动态规划-[解题报告] C++
2013
12-23

HDU 1876 机器人系列2-动态规划-[解题报告] C++

机器人系列2

问题描述 :

这又是一个简单的游戏,你控制一个机器人从一个棋盘的起始点(1,1)走到棋盘的终点(n,m)。游戏的规则描述如下:
1.机器人一开始在棋盘的起始点(1,1)并有起始点所标有的能量。
2.机器人只能向右或者向下走,并且每走一步消耗一单位能量。
3.只有当机器人消耗完能量时才能获得相应格子上的能量。
请问机器人到达终点的过程中最多有几次完全消耗完能量,消耗完这么多次能量的方式有几种。

输入:

输入
第一行输入一个整数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

样例输出:

3 4

< [if gte mso 9]>MicrosoftInternetExplorer402DocumentNotSpecified7.8Normal0

#include <stdio.h>
__int64 map[105][105];
__int64 dp[105][105];
__int64 cnt[105][105];
void Test(__int64 n,__int64 m)
{
	__int64 i,j;
	printf("/n");
	for (i=0;i<n;i++)
	{
		for (j=0;j<m;j++)
		{
			printf("%I64d ",cnt[i][j]);
		}
		printf("/n");
	}
}
int Dis(int x1,int y1,int x2,int y2)
{
	return y2-y1+x2-x1;
}
int main()
{
	__int64 i,j,T,n,m,k;
	scanf("%I64d",&T);
	while(T--)
	{
		scanf("%I64d%I64d",&n,&m);
		for (i=0;i<n;i++)
		{
			for (j=0;j<m;j++)
			{
				scanf("%I64d",&map[i][j]);
			}
		}
		for (i=0;i<n;i++)
		{
			for (j=0;j<m;j++)
			{
				dp[i][j]=0;
				cnt[i][j]=0;
			}
		}
		dp[0][0]=1;
		cnt[0][0]=0;
		for (i=0;i<n;i++)
		{
			for (j=0;j<m;j++)
			{
				if (dp[i][j]==0 || map[i][j]==0) continue;
				for (k=0;k<=map[i][j];k++)
				{
					if (i+k<n && j+map[i][j]-k<m) 
					{
						if (cnt[i+k][j+map[i][j]-k]<cnt[i][j]+1) 
						{
							dp[i+k][j+map[i][j]-k]=dp[i][j];
							cnt[i+k][j+map[i][j]-k]=cnt[i][j]+1;
						} 
						else if (cnt[i+k][j+map[i][j]-k]==cnt[i][j]+1)
						{
							dp[i+k][j+map[i][j]-k]+=dp[i][j];
						}		
					}
				//	Test(n,m);
				}
			}
		}
		__int64 s=0;
		__int64 p=0;
		for (i=0;i<n;i++)
		{
			for (j=0;j<m;j++)
			{
				if (s<cnt[i][j] && (map[i][j]!=0 || (i==n-1 && j==m-1)) && Dis(i,j,n-1,m-1)<=map[i][j]) 
				{
					s=cnt[i][j];
					p=dp[i][j];
				}
				else if (s==cnt[i][j] && (map[i][j]!=0 || (i==n-1 && j==m-1)) && Dis(i,j,n-1,m-1)<=map[i][j])
				{
					p=p+dp[i][j];
				}
			}
		}
		printf("%I64d %I64d/n",s,p);
	}
	return 0;
}

解题报告转自:http://blog.csdn.net/magicnumber/article/details/6195087


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

  3. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。