放牧代码和思想
专注自然语言处理、机器学习算法
    时间有限,只有GitHub上的issue能及时处理,大约每周末一次。另外,不要叫我楼主,谢谢。

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版)》

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机