POJ3176 Cow Bowling dp

网址:https://vjudge.net/problem/POJ-3176

题意:

给出一个三角形,第$i$行有$i$个数,从第一行出发每次只能到第$i+1$行的第$i$个数或者第$i+1$行的第$i+1$个数,求轨迹上的数的和的最大值。

题解:

$dp[i][j]$指的是到了第i行第j个数的路径上的数的和的最大值。

故从$2$行开始,对于第$i$行的第$j$个数,它的路径只会来自第$i-1$行第$j$个或第$i-1$行的第$j-1$个,故$dp[i][j]=max[dp[i-1][j],dp[i-1][j-1]]+num[i][j]$;即从两条路径中选一条大的路径。枚举$i$从$2$至$n$,然后从$dp[n]$中找出一个最大值即可。

因为第$i$行的状态只和第$i-1$行有关,故使用滚动数组优化。

$dp[i]$为到了某一行的第i个数时路径上的数的和的最大值。

从$2$行开始,对于第$k$行的第$i$个数,它的路径只会来自第$i$个或第$i-1$个,故$dp[j]=max[dp[j],dp[j-1]]+num[j]$;即从两条路径中选一条大的路径。$j$从$k$开始更新到$1$,避免了因为先更新了前面的,在后面处理$dp[j]$的时候重复计算导致错误。

AC代码:(标记的值和题解的说法不一样)

#include <iostream>
#include <algorithm>
using namespace std;
int num[355];
int dp[355];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j <= i; ++j)
			cin >> num[j];
		for (int j = i + 1; j > 0; --j)
			dp[j] = max(dp[j], dp[j - 1]) + num[j - 1];//从上一层到下一层时,只能是从正上方和左上方
		//只与上一层有关,故使用dp[i]和dp[i-1]更新下一层,从后向前更新,因为若从前往后,dp[i-1]将不是上一行的值
	}
	int ans = 0;
	for (int i = 1; i <= n; ++i)
		ans = max(ans, dp[i]);//在最后一行得到最大值
	cout << ans << endl;
	return  0;
}

 

上一篇:差分约束系统


下一篇:Luogu P2886 [USACO07NOV\]牛继电器Cow Relays|最短路,倍增