hdu 1913 computer 解题报告
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1913
题意: 这道题就是说有个人想在不同的时期分别买一台新电脑（具体一共买几台不知道），希望能够使用这些电脑来工作N年。每台电脑每年都有维护费用，你每买一台电脑时，都要花固定的成本C（就是用来买台电脑的钱了），你使用电脑工作N年，你要花的钱就是买电脑的固定成本，再加上总的维修费用。你要写一个程序，求出使用N年的最少钱是多少。
算法:部分贪心+一维dp
AC代码:
#include <stdio.h>
#define M 1999
#define inf 100000000
int data[M][M];
int cost[M];
int main()
{
// freopen("1.txt", "r", stdin);
int i, j;
int c; //新买的一台电脑的价格
int n; //n 个周期
while (scanf("%d%d", &c, &n) != EOF)
{
for (i = 1; i <= n; i++)
{
for (j = i; j <= n; j++)
{
scanf("%d", &data[i][j]);
data[i][j] += c;
}
}
cost[0] = 0;
for (i = 1; i <= n; i++)
{
cost[i] = inf;
for (j = 0; j < i; j++)
{
//一维dp的应用
//需要换电脑的时候
//部分贪心
if (data[j + 1][i] + cost[j] < cost[i])
{
cost[i] = data[j + 1][i] + cost[j];
}
}
}
printf("%d/n", cost[n]);
}
return 0;
}