acm 1151: 款待奶牛(treat)
FJ有n（1≤n≤2000）个美味的食物，他想卖掉它们来赚钱给奶牛。这些食物放在一些箱子里，它们有些有趣的特性：
（1）这些食物被编号为1～n，每一天FJ可以从这排箱子的头部或者尾部取出食物去卖；
（2）这些食物放得越久，年龄越大，价值越大，食物i有一个初始的价值V(i)；
（3）放了a天后，年龄为a，食物最终的价值为V(i)×a。
给定每一个食物的初始价值v(i)，请求出FJ卖掉它们后可以获得的最大价值，第一天出售的食物的年龄为1，此后每增加一天食物的年龄就增加1。
输入
第1行：一个整数n；
第i+l行：每行为食物i的初始价值V(i)。
输出
1行：FJ最终可以获得的最大价值。
样例输入
5
1
3
1
5
2
样例输出
43
下面是我写的代码 第一思路 贪心
#include
int main()
{
int n,i,count;
int s=0;
int a[2001];
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1,count=1;i<=n;i++,count++)
{
if(a[i]<a[n])
s=s+count*a[i];
else {
s=s+count*a[n];
n--;
i--;
}
}
printf("%d\n",s);
return 0;
}
但是没有通过，所以考虑用动态规划，下面是我的代码
#include<iostream>
#include<algorithm>
using namespace std;
int m,n,dp[2000][2000],a[2000],b[2000],Max=0;
int main()
{ int i,j;
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i];
a[0]=0;
for(i=0;i<=n;i++)
{dp[0][i]=0;}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{ if(j>=i)
dp[i][j]=max(dp[i-1][j]+(n+i-j-1)*a[i-1],dp[i][j+1]+(n+i-j-1)*a[j+1]);
cout<<dp[i][j]<<endl;
}
}
for(i=1;i<=n;i++)
{
b[i]=dp[i][i]+a[i]*n;
}
for(i=1;i<=n;i++)
{if(Max<b[i])
Max=b[i];
}
cout<<Max<<endl;
return 0;
}
问题有2个：为什么这题贪心不可行。
代码二 用例子 运算是42 但是我找不出问题，寻求帮助。
ps：新人没有悬赏金.。。。。希望得到大牛帮助。
代码2的补充解释
dp[i][j]=max(dp[i-1][j]+(n+i-j-1)*a[i-1],dp[i][j+1]+(n+i-j-1)*a[j+1]);
//dp[i][j] i从前往后第i位 j是从前往后第j位（j>=i） 要得到dp[i][j] 就是在他的前2个状态中寻得一个大值（dp[i-1][j]+(n+i-j-1)*a[i-1],dp[i][j+1]+(n+i-j-1)*a[j+1]） 其中 （n+i-j-1）是第几天
最终结果肯定停留在某一个数字上 比如 例题里面 5（ 1 3 1 5 2），停留在dp[4][4]上面 要得到这个结果 要将所有dp[I][I]+n* a[I]
的值进行比较 取得最大值 也就是我代码下半部分的目的
贪心 -- 如果左边和右边相等，你怎么能保证取右面的值是最优的呢？