TOJ 1158 Computers DP

た入场券 2022-05-17 01:14 143阅读 0赞

## **1158: 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

**样例输出**

**提示**

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

题意：每台电脑价钱一样，买一台要花费c元，DP取舍买新电脑，还是保养旧电脑，找出最小花费。

#include <stdio.h>
    #include <algorithm>
    using namespace std;
    int sum[1005][1005];
    int main()
    {
    	int c,n,i,j;
    	while (scanf("%d",&c)!=EOF)
    	{
    		scanf("%d",&n);
    		for(i=0;i<n;i++)
    		{
    			for(j=i;j<n;j++)
    				scanf("%d",&sum[i][j]);
    		}
    		for(i=0;i<n;i++)
    		{
    			for(j=i;j<n;j++)
    			{
    				if(i==0)
    				sum[i][j]=c+sum[i][j];
    				else
    				sum[i][j]=min(sum[i-1][i-1]+c+sum[i][j],sum[i-1][j]);
    			}
    		}
    		printf("%d\n",sum[n-1][n-1]);
    	}
    	return 0;
    }