POJ3176-Cow Bowling

来源:互联网 时间:1970-01-01

转载请注明出处:優YoU  http://user.qzone.qq.com/289065406/blog/1300453935

大致题意:

输入一个n层的三角形,第i层有i个数,求从第1层到第n层的所有路线中,权值之和最大的路线。

规定:第i层的某个数只能连线走到第i+1层中与它位置相邻的两个数中的一个。

 

解题方法:

用二维数组way[][]靠左存储三角形内的数据,那么连线规则变更为

way[i][j] → Way[i+1][j]

Way[i][j] → Way[i+1][j+1]

 

注意:way[][]初始化为输入时的三角形数值,此时way[i][j]表示该点位置上的权值,没输入的位置初始化为0。

 

解题思路:

动态规划。

way[i][j]表示以第i行j列的位置作为终点的路线的最大权值。 (注意区分初始化时的意义)

那么way[i][j]的最大值取决于way[i-1][j-1]和way[i-1][j],从这两者之间筛选出最大值,加到way[i][j]上,即为way[i][j]的最大权值。

最后只要比较第n行中所有位置的权值way[n][j],最大的一个即为所求。

 

顺带一提,POJ1163和这题是双子题,两道题基本一模一样,区别仅仅在于n的取值范围。所以说如果是用动态申请二维数组的同学,就可以直接把代码复制到POJ1163提交AC了。

 

再顺便说一下动态申请二维数组的方法。

C++的new函数是无法直接申请二维空间的,但是可以间接申请。

以我的程序为例,先申请一个“指向一维指针数组”的二维指针

Int **way=new int*[n+1];

这个数组way[]的每一个元素都是一个指针

再利用for循环,逐行申请空间,使每一个元素(指针)指向一个“一维数组”

Way[i]=new int[i+2];   //这个大小是根据本题而决定的一个小优化,不同的题具体申请大小

 

这两次操作相当于先申请了二维数组way的行数,再逐行申请列数,这就相当于间接申请了一个二维数组,而且每行的列数还可以不同,优化了空间使用率。

 1 //Memory Time 
2 //468K 172MS
3
4 #include<iostream>
5 using namespace std;
6
7 int max(int a,int b)
8 {
9 return a>b?a:b;
10 }
11
12 int main(int i,int j)
13 {
14 int n;
15 while(cin>>n)
16 {
17 int **way=new int*[n+1]; //动态申请二维数组的第一维,每个元素都是一个一维数组的指针
18
19 /*Input & Initial*/
20
21 for(i=0;i<=n;i++)
22 {
23 way[i]=new int[i+2]; //动态申请二维数组的第二维,每一行的空间
24 for(j=0;j<=i+1;j++)
25 way[i][j]=0; //不能用memset初始化
26
27 if(i!=0)
28 for(j=1;j<=i;j++)
29 cin>>way[i][j];
30 }
31
32 /*Dp*/
33
34 int max_weight=0;
35 for(i=1;i<=n;i++)
36 for(j=1;j<=i;j++)
37 {
38 way[i][j] += max(way[i-1][j-1],way[i-1][j]);
39
40 if(i==n && max_weight<way[i][j])
41 max_weight=way[i][j];
42 }
43
44 cout<<max_weight<<endl;
45
46 delete[] way;
47 }
48 return 0;
49 }
我的所有ACM解题报告:http://user.qzone.qq.com/289065406/blog/1301632863我的CSDN:http://hi.csdn.net/invite.php?u=10114444&c=57929f66dd919f2b我的新浪微博:http://weibo.com/lyy289065406我的腾讯微博:http://t.qq.com/liao5422我的QQ空间:http://user.qzone.qq.com/289065406我的百度空间:http://hi.baidu.com/you289065406/home我的金山网盘:http://www.kuaipan.cn/register/?invite=evpga1


相关阅读:
Top