POJ 3176 Cow Bowling 题解 《挑战程序设计竞赛(第2版)》

2.3 记录结果再利用的“动态规划” 基础的动态规划算法

POJ 3176 Cow Bowling

奶牛保龄球：金字塔形的保龄球中从顶往下撞击，每次只能撞击左下或右下两个，求所有撞到得分的最高值。

最基础的dp吧，用dp[i][j]表示第i行第j个点处能得到的最高分，由顶往下推导更新此dp即可：

#include <iostream>
#include <algorithm>
using namespace std;

#define MAX_CASES 350

int score[MAX_CASES][MAX_CASES];
int dp[MAX_CASES][MAX_CASES];

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
	int N;
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j <= i; ++j)
		{
			cin >> score[i][j];
		}
	}

	dp[0][0] = score[0][0];
	for (int i = 0; i < N - 1; ++i)
	{
		for (int j = 0; j <= i; ++j)
		{
			dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + score[i + 1][j + 1]);
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + score[i + 1][j]);
		}
	}

	cout << *max_element(dp[N -1], dp[N -1] + N) << endl;
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("out.txt");
#endif
    return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3176 Cow Bowling 题解 《挑战程序设计竞赛(第2版)》