P2858 [USACO06FEB]Treats for the Cows G/S

我们首先一看到题目，很明显就是区间dp。

题目思路

这是一道区间dp的裸题，不过这题是要倒着推，只剩最后一个数时开始递推。

我们令dp[l][r]是区间[l,r]的最大值。

显然对于当前区间[l,r],只能从左边或右边取。

显然有: dp[l][r]=max(dp[l-1][r]+v[l]*(n-len+1),dp[l][r-1]+v[r]*(n-len+1))

OK，上代码