首页 > ACM题库 > HDU-杭电 > hdu 2391 Filthy Rich-动态规划-[解题报告]C++
2014
01-05

hdu 2391 Filthy Rich-动态规划-[解题报告]C++

Filthy Rich

问题描述 :

They say that in Phrygia, the streets are paved with gold. You’re currently on vacation in Phrygia, and to your astonishment you discover that this is to be taken literally: small heaps of gold are distributed throughout the city. On a certain day, the Phrygians even allow all the tourists to collect as much gold as they can in a limited rectangular area. As it happens, this day is tomorrow, and you decide to become filthy rich on this day. All the other tourists decided the same however, so it’s going to get crowded. Thus, you only have one chance to cross the field. What is the best way to do so?

Given a rectangular map and amounts of gold on every field, determine the maximum amount of gold you can collect when starting in the upper left corner of the map and moving to the adjacent field in the east, south, or south-east in each step, until you end up in the lower right corner.

输入:

The input starts with a line containing a single integer, the number of test cases.
Each test case starts with a line, containing the two integers r and c, separated by a space (1 <= r, c <= 1000). This line is followed by r rows, each containing c many integers, separated by a space. These integers tell you how much gold is on each field. The amount of gold never negative.
The maximum amount of gold will always fit in an int.

输出:

The input starts with a line containing a single integer, the number of test cases.
Each test case starts with a line, containing the two integers r and c, separated by a space (1 <= r, c <= 1000). This line is followed by r rows, each containing c many integers, separated by a space. These integers tell you how much gold is on each field. The amount of gold never negative.
The maximum amount of gold will always fit in an int.

样例输入:

1
3 4
1 10 8 8
0 0 1 8
0 27 0 4

样例输出:

Scenario #1:
42

直接遍历

#include<stdio.h>
#include<string.h>
int map[1010][1010],dp[1010][1010];
int main()
{
	int i,j,n,m,t,op=1;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		for(i=0;i<n;i++)
			for(j=0;j<m;j++)
				scanf("%d",&map[i][j]);
			memset(dp,0,sizeof(dp));
			dp[0][0]=map[0][0];
			for(i=0;i<n;i++)
				for(j=0;j<m;j++)
				{
					if(i-1>=0&&dp[i][j]<map[i][j]+dp[i-1][j])
						dp[i][j]=map[i][j]+dp[i-1][j];
					if(j-1>=0&&dp[i][j]<map[i][j]+dp[i][j-1])
						dp[i][j]=map[i][j]+dp[i][j-1];
					if(i-1>=0&&j-1>=0&&dp[i][j]<map[i][j]+dp[i-1][j-1])
						dp[i][j]=map[i][j]+dp[i-1][j-1];
				}
				printf("Scenario #%d:\n",op++);
				printf("%d\n\n",dp[n-1][m-1]);
	}
	return 0;
}

解题转自:http://blog.csdn.net/aixiaoling1314/article/details/8964894


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

  3. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n