题意:给定n个数
每次可以从头或者尾取出数据
于是按取出来得顺序,就可以排成一个数列,假设这个数列为
a1,a2,a3,a4.......an
现在我们假设按照取出来的顺序有一个权值
w=a1*1+a2*2+a3*3+....an*n
现在需要编程求出,如何控制取数的顺序,让w的值最大
思路:
首先我以为是贪心,每次取最小值出来就可以了。。可是贪心的思路是错的。。有反例的
然后看到帖子上有人说这个题是动态规划,于是我就朝动态规划的方向进行构思
其实这个动态转移方程还比较好想,可以开一个二维的数组用来存当前的最大值
由于每次要么从头取,要么从尾取,于是状态转移方程为:
dp[i][j]=max(dp[i-1][j]+v[i]*(i+j),dp[i][j-1]+v[n-j+1]*(i+j));
然后适当注意一下边界条件就可以AC了~~
my ugly code:
#include<stdio.h> #include<algorithm> using namespace std; int dp[2005][2005]; int v[2005]; int max(int a,int b) { if(a>b) return a; else return b; } int main() { int i,j,n; while(scanf("%d",&n)!=EOF) { for(i=1;i<=n;i++) scanf("%d",&v[i]); memset(dp,0,sizeof(dp)); for(i=0;i<=n;i++) for(j=0;i+j<=n;j++) { if(i==0&&j==0) dp[i][j]=0; else if(i==0&&j!=0) dp[i][j]=max(dp[i][j],dp[i][j-1]+v[n-j+1]*(i+j)); else if(i!=0&&j==0) dp[i][j]=max(dp[i][j],dp[i-1][j]+v[i]*(i+j)); else dp[i][j]=max(dp[i-1][j]+v[i]*(i+j),dp[i][j-1]+v[n-j+1]*(i+j)); } int ans=0; for(i=0;i<=n;i++) if(dp[i][n-i]>ans) ans=dp[i][n-i]; printf("%d/n",ans); } return 0; }