首页 > 专题系列 > Java解POJ > POJ 2229 Sumsets [解题报告] Java
2013
11-10

POJ 2229 Sumsets [解题报告] Java

Sumsets

问题描述 :

Farmer John commanded his cows to search for different sets of numbers that sum to a given number. The cows use only numbers that are an integer power of 2. Here are the possible sets of numbers that sum to 7:

1) 1+1+1+1+1+1+1

2) 1+1+1+1+1+2

3) 1+1+1+2+2

4) 1+1+1+4

5) 1+2+2+2

6) 1+2+4

Help FJ count all possible representations for a given integer N (1 <= N <= 1,000,000).

输入:

A single line with a single integer, N.

输出:

The number of ways to represent N as the indicated sum. Due to the potential huge size of this number, print only last 9 digits (in base 10 representation).

样例输入:

7

样例输出:

6

解题代码:

//* @author: [email protected]
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  int[] arr=new int[1000001];
  arr[1]=1;
  arr[2]=2;
  for(int i=3;i< 1000001;i++)
   {
	if(i%2==0) arr[i]=(arr[i-2]+arr[i/2])%1000000000;
	else arr[i]=arr[i-1];
   }
  int a=in.nextInt();
  System.out.println(arr[a]);
 }
}

  1. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

  2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

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