poj 3176 Cow Bowling dp

缘起

日常浪费生命 poj 3176 Cow Bowling

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
输入一个n层的三角形，第i层有i个数，求从第1层到第n层的所有路线中，权值之和最大的路线。
规定：第i层的某个数只能连线走到第i+1层中与它位置相邻的两个数中的一个。

【输入】
n(1 <= N <= 350), 然后n行每行代表该行的数字, 数字范围是（0~99）

【输出】
最大和

【样例输入】
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

【样例输出】
30

【hint】
7-->3-->8-->7-->5

【限制】
1s

【来源】
USACO 2005 December Bronze

典型的dp啦（此题算比较经典的dp了）~ 令dp[i][j]表示到达第i层的从左往右第j个数为止的最大和. 则显然有dp公式如下

1
dp[i][j] = max{dp[i-1][j-1],dp[i-1][j]} , 当然, 需要dp[i-1][j-1]和dp[i-1][j]都存在

那么, 我们可以写下如下ac程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL

int a[355][355],dp[355][355], n;

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d", &n);
	for (int i = 1; i<=n;i++)
	{
		for (int j = 1; j<=i; j++)
		{
			scanf("%d", a[i]+j);
		}
	}
	dp[1][1] = a[1][1];
	for (int i = 2; i<=n; i++)
	{
		for (int j = 1; j<=i; j++)
		{
			dp[i][j] = max(dp[i-1][j-1], dp[i-1][j])+a[i][j];
		}
	}
	int ans = 0;
	for (int i = 1;i<=n;i++)
	{
		ans = max(ans, dp[n][i]);
	}
	printf("%d\n", ans);
	return 0;
}

ac情况

Status Accepted
Time 32ms
Memory 1060kB
Length 629
Lang C++
Submitted 2019-08-26 09:31:53
Shared
RemoteRunId 20801271