2013
11-12

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