首页 > 专题系列 > Java解POJ > POJ 3486 Computers [解题报告] Java
2013
11-12

POJ 3486 Computers [解题报告] Java

Computers

问题描述 :

Everybody is fond of computers, but buying a new one is always a money challenge. Fortunately, there is always a convenient way to deal with. You can replace your computer and get a brand new one, thus saving some maintenance cost. Of course, you must pay a fixed cost for each new computer you get.

Suppose you are considering an n year period over which you want to have a computer. Suppose you buy a new computer in year y, 1<=y<=n Then you have to pay a fixed cost c, in the year y, and a maintenance cost m(y,z) each year you own that computer, starting from year y through the year z, z<=n, when you plan to buy – eventually – another computer.

Write a program that computes the minimum cost of having a computer over the n year period.

输入:

The program input is from a text file. Each data set in the file stands for a particular set of costs. A data set starts with the cost c for getting a new computer. Follows the number n of years, and the maintenance costs m(y,z), y=1..n, z=y..n. The program prints the minimum cost of having a computer throughout the n year period.

White spaces can occur freely in the input. The input data are correct and terminate with an end of file.

输出:

For each set of data the program prints the result to the standard output from the beginning of a line.

样例输入:

3
3
5 7 50
6 8
10

样例输出:

19

温馨提示:

An input/output sample is shown above. There is a single data set. The cost for getting a new computer is c=3. The time period n is n=3 years, and the maintenance costs are:

  • For the first computer, which is certainly bought: m(1,1)=5, m(1,2)=7, m(1,3)=50,
  • For the second computer, in the event the current computer is replaced: m(2,2)=6, m(2,3)=8,
  • For the third computer, in the event the current computer is replaced: m(3,3)=10.

解题代码:

/* @author: */
import java.util.Scanner;   
import java.util.Arrays;
public class Main {   
   

 public static void main(String[] args) {   
    Scanner sc = new Scanner(System.in);   
    int n,c;
    int m[][]=new int[1003][1003];
    int f[]=new int[1003];
    while(sc.hasNext()){
          c=sc.nextInt();
          n=sc.nextInt();
          for(int i=0;i< m.length;i++)
             Arrays.fill( m[i],0);
          for(int i=1;i<=n;i++){
               for(int j=i;j<=n;j++)
                 m[i][j]=sc.nextInt();
                    
          }
          for(int i=1;i<=n;i++){
               f[i]=c+m[1][i];        
          }
          for(int i=2;i<=n;i++){
               for(int j=i;j<=n;j++){
                    if(f[j]>f[i-1]+c+m[i][j])
                         f[j]=f[i-1]+c+m[i][j];        
               }        
          }
          System.out.printf("%d\n",f[n]);                  
    }
    }
}

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

  2. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。

  3. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  4. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。