首页 > 专题系列 > Java解POJ > POJ 1090 Chain [解题报告] Java
2013
11-09

POJ 1090 Chain [解题报告] Java

Chain

问题描述 :

Byteland had not always been a democratic country. There were also black pages in its book of history. One lovely day general Bytel − commander of the junta which had power over Byteland −− decided to finish the long−lasting time of war and released imprisoned activists of the opposition. However, he had no intention to let the leader Bytesar free. He decided to chain him to the wall with the bytish chain. It consists of joined rings and the bar fixed to the wall. Although the rings are not joined with the bar, it is hard to take them off.

‘General, why have you chained me to the prison walls and did not let rejoice at freedom!’ cried Bytesar.

‘But Bytesar, you are not chained at all, and I am certain you are able to take off the rings from the bar by yourself.’ perfidiously answered general Bytel, and he added ‘But deal with that before a clock strikes the cyber hour and do not make a noise at night, otherwise I will be forced to call Civil Cyber Police.’

Help Bytesar! Number the following rings of the chain with integers 1,2,…,n. We may put on and take off these rings according to the following rules:

.only one ring can be put on or taken off from the bar in one move,

.the ring number 1 can be always put on or taken off from the bar,

.if the rings with the numbers 1,…,k−1 (for 1<= k < n) are taken off from the bar and the ring number k is put on, we can put on or take off the ring number k+1.

Write a program which:

.reads from std input the description of the bytish chain,

.computes minimal number of moves necessary to take off all rings of the bytish chain from the bar,

.writes the result to std output.

输入:

In the first line of the input there is written one integer n, 1 <= n <= 1000. In the second line there are written n integers o1,o2,...,on (each of them is either 0 or 1) separated by single spaces. If oi=1, then the i−th ring is put on the bar, and if oi=0, then the i−th ring is taken off the bar.

输出:

The output should contain exactly one integer equal to the minimal number of moves necessary to take off all the rings of the bytish chain from the bar.

样例输入:

4
1 0 1 0

样例输出:

6

解题代码:

/* @author: */
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
 public static void main(String[] args){
 Scanner stdin=new Scanner(System.in);
 int n=stdin.nextInt();
 int[] a=new int[n],b=new int[n];
 for(int i=0;i< n;i++)a[i]=stdin.nextInt();
  b[0]=a[n-1];
  for(int i=1;i< n;i++){
    b[i]=b[i-1]^a[n-1-i];
  }
  BigInteger ans=new BigInteger("0"),two=new BigInteger("2");
 for(int i=0;i< n;i++){
   ans=ans.multiply(two);
   if(b[i]==1)
	ans=ans.add(BigInteger.ONE);
 }
  System.out.println(ans);
  }
}

  1. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?