首页 > ACM题库 > HDU-杭电 > hdu 1913 Computers-动态规划-[解题报告]C++
2013
12-27

hdu 1913 Computers-动态规划-[解题报告]C++

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.

关键是理解意思。要点一,这个题目要在所有的n年都有电脑,也就是说第一年的时候必定先买电脑;要点二,到第i年的最少花费,必然是不知道从第几年买电脑,并且一直使用到了第i年;要点三,矩阵中的信息是从第i年买电脑,到第j年总的维修费,只是维修费,买电脑的钱没在里面。题目很黑啊,没给数据范围,我的程序到1000就过了。

#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;
}

解题转自:http://blog.csdn.net/killer_in_silence/article/details/10400305


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

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

  3. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  4. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.