首页 > 专题系列 > Java解POJ > POJ 3186 Treats for the Cows [解题报告] Java
2013
11-12

POJ 3186 Treats for the Cows [解题报告] Java

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
 {
	InputStreamReader is=new InputStreamReader(System.in);
	BufferedReader in=new BufferedReader(is);
	String s=in.readLine();
	int a=Integer.parseInt(s);
	int[] arr=new int[a];
	int[][] ds=new int[a][a];
	for(int i=0;i< a;i++)
	{
		s=in.readLine();
		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)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮