Computers
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 454 Accepted Submission(s): 155
Problem Description
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.
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.
Input
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.
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.
Output
For each set of data the program prints the result to the standard output from the beginning of a line.
Sample Input
3 3 5 7 50 6 8 10
Sample Output
19HintAn 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.
Source
Recommend
lcy
dp[i][j],表示第i天，买的电脑用到j天的费用，j>=i;
转移方程
i==j时
for(k=1;k<=i-1;k++)
dp[i][j]=min(dp[i][j],dp[k][j-1]+m[i][j]+c);
dp[i][j]=min(dp[i][j],dp[k][j-1]+m[i][j]+c);
j>i时
dp[i][j]=min(dp[i][j],dp[i][j-1]+m[i][j]);
代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#define inf 0x3f3f3f3f
using namespace std;
int cost[1005][1005];
int m[1005][1005];
int dp[1005][1005];
int main()
{
int c;
while(scanf("%d",&c)!=EOF)
{
int n;
scanf("%d",&n);
memset(cost,0,sizeof(cost));
int i,j;
for(i=1;i<=n;i++)
{
for(j=i;j<=n;j++)
scanf("%d",&cost[i][j]);
}
for(i=1;i<=n;i++)
{
for(j=i;j<=n;j++)
{
m[i][j]=cost[i][j]-cost[i][j-1];
}
}
memset(dp,inf,sizeof(dp));
for(i=1;i<=n;i++)
{
if(i==1)
dp[1][i]=c+m[1][i];
else
dp[1][i]=dp[1][i-1]+m[1][i];
}
for(i=2;i<=n;i++)
{
for(j=i;j<=n;j++)
{
if(j>i)
dp[i][j]=min(dp[i][j],dp[i][j-1]+m[i][j]);
else
{
int k;
for(k=1;k<=i-1;k++)
dp[i][j]=min(dp[i][j],dp[k][j-1]+m[i][j]+c);
}
}
}
int mm=inf;
for(i=1;i<=n;i++)
if(dp[i][n]<mm)
mm=dp[i][n];
printf("%d\n",mm);
}
return 0;
}