|
|
思路：
f[倒数第几天][队列头的位置] = { 该状态下所产生的最大值 }
状态转移：
f[i][j] = max {
V[j + i]*(N - i) + f[i - 1][j],
f[i - 1][j + 1] + V[j]*(N - i)
}
代码：
 #include <stdio.h>
inline int max(int a, int b)
   {
 return a > b ? a : b;
 }
int N, V[2048], f[2][2048], *cur, *pre;
int main()
{
int i, j;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d", &N);
  for (i = 0; i < N; i++) {
scanf("%d", &V[i]);
f[1][i] = V[i]*N;
 }
for (i = 1; i < N; i++) {
pre = f[i & 1];
cur = f[(i + 1) & 1];
for (j = 0; j < N - i; j++)
cur[j] = max(pre[j] + V[j + i]*(N - i), pre[j + 1] + V[j]*(N - i));
}
printf("%d\n", cur[0]);
return 0;
}
|