2013
12-27

# 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.

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.

3
3
5 7 50
6 8
10

19

Hint

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.


#include<iostream>
#include<stdio.h>
using namespace std;
int map[1005][1005];
int dp[1005];
int mini(int a,int b)
{
if(a<b)
return a;
return b;
}
int main()
{
int c,n,start,end,i,j;
while(scanf("%d",&c)!=EOF)
{
scanf("%d",&n);
for(start=1;start<=n;start++)
for(end=start;end<=n;end++)
scanf("%d",&map[start][end]);
dp[0]=0;
for(i=1;i<=n;i++)
{
dp[i]=100000000;
for(j=0;j<i;j++)
dp[i]=mini(dp[i],dp[j]+c+map[j+1][i]);
}
cout<<dp[n]<<endl;
}
return 0;
}

1. 第一题是不是可以这样想，生了n孩子的家庭等价于n个家庭各生了一个1个孩子，这样最后男女的比例还是1:1

2. 题本身没错，但是HDOJ放题目的时候，前面有个题目解释了什么是XXX定律。
这里直接放了这个题目，肯定没几个人明白是干啥