2013
11-12

# Treats for the Cows

FJ has purchased N (1 <= N <= 2000) yummy treats for the cows who get money for giving vast amounts of milk. FJ sells one treat per day and wants to maximize the money he receives over a given period time.

The treats are interesting for many reasons:

• The treats are numbered 1..N and stored sequentially in single file in a long box that is open at both ends. On any day, FJ can retrieve one treat from either end of his stash of treats.
• Like fine wines and delicious cheeses, the treats improve with age and command greater prices.
• The treats are not uniform: some are better and have higher intrinsic value. Treat i has value v(i) (1 <= v(i) <= 1000).
• Cows pay more for treats that have aged longer: a cow will pay v(i)*a for a treat of age a.

Given the values v(i) of each of the treats lined up in order of the index i in their box, what is the greatest value FJ can receive for them if he orders their sale optimally?

The first treat is sold on day 1 and has age a=1. Each subsequent day increases the age by 1.

Line 1: A single integer, N

Lines 2..N+1: Line i+1 contains the value of treat v(i)

Line 1: The maximum revenue FJ can achieve by selling the treats

5
1
3
1
5
2

43

Explanation of the sample:

Five treats. On the first day FJ can sell either treat #1 (value 1) or treat #5 (value 2).

FJ sells the treats (values 1, 3, 1, 5, 2) in the following order of indices: 1, 5, 2, 3, 4, making 1×1 + 2×2 + 3×3 + 4×1 + 5×5 = 43.

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
public static void main(String[] args) throws IOException
{
int a=Integer.parseInt(s);
int[] arr=new int[a];
int[][] ds=new int[a][a];
for(int i=0;i< a;i++)
{
arr[i]=Integer.parseInt(s);
}
System.out.println(f(arr,0,a-1,ds));

}

public static int f(int[] arr,int l,int r,int[][] ds)
{
if(ds[l][r]!=0) return ds[l][r];
int n=arr.length;
if(l==r) return ds[l][l]=n*arr[l];
int w=f(arr,l+1,r,ds)+(n-r+l)*arr[l];
int o=f(arr,l,r-1,ds)+(n-r+l)*arr[r];
ds[l][r]=Math.max(w, o);
return ds[l][r];
}
}

1. 站长，你好！
你创办的的网站非常好，为我们学习算法练习编程提供了一个很好的平台，我想给你提个小建议，就是要能把每道题目的难度标出来就好了，这样我们学习起来会有一个循序渐进的过程！

2. a是根先忽略掉，递归子树。剩下前缀bejkcfghid和后缀jkebfghicd，分拆的原则的是每个子树前缀和后缀的节点个数是一样的，根节点出现在前缀的第一个，后缀的最后一个。根节点b出现后缀的第四个位置，则第一部分为四个节点，前缀bejk，后缀jkeb，剩下的c出现在后缀的倒数第2个，就划分为cfghi和 fghic，第3部分就为c、c

3. #include <stdio.h>
int main(void)
{
int arr[] = {10,20,30,40,50,60};
int *p=arr;
printf("%d,%d,",*p++,*++p);
printf("%d,%d,%d",*p,*p++,*++p);
return 0;
}

为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下？

4. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮