当前位置: 代码迷 >> 综合 >> POJ 3186 - Treats for the Cows
  详细解决方案

POJ 3186 - Treats for the Cows

热度:26   发布时间:2023-12-24 11:21:55.0

题目大意:有n头牛排着队,每天从头或为取一只牛出来卖,能卖出的价格为牛的价值乘上这是第几天,求把n头牛卖出最多能得到多少钱。

解题思路:不能用贪心,因为当存在首尾价值一样的,会出问题。用dp看题解的。。。dp[i][j]表示从头取了i个,从尾取了j个时的最大价值。所以i+j<=n。而dp[i][j]是由dp[i-1][j]或dp[i][j-1]得到的。所以第一个循环0...n,第二个循环0...n-i。如果i或j为0时另外判断。

ac代码:

#include <iostream>
#include <cstring>
using namespace std;
int value[2005], n, dp[2005][2005], Max;
int main()
{while (scanf("%d", &n)!=EOF){memset(dp, 0, sizeof(dp));dp[0][0] = 0;for (int i=1; i<=n; i++)scanf("%d", &value[i]);for (int i=0; i<=n; i++)for (int j=0; j<=n-i; j++){if (!i && !j)continue;else if (i && !j)dp[i][j] = max(dp[i][j], dp[i-1][j]+value[i]*i);else if (!i && j)dp[i][j] = max(dp[i][j], dp[i][j-1]+value[n-j+1]*j);elsedp[i][j] = max(dp[i-1][j]+value[i]*(i+j), dp[i][j-1]+value[n-j+1]*(i+j));}Max = 0;for (int i=0; i<=n; i++)Max = max(Max, dp[i][n-i]);printf("%d\n", Max);}
return 0;
}