Poj-3486-computers[dynamic planning]

The original title is

The original topic is here

The main idea of the topic

One should ensure that he is n Computers are available every year in the middle of the year , He has two choices every year , Or buy a new computer , Or repair the computer you used before . The money for a new computer is fixed , The money for repairing the computer is m[y][z],y Is the year the computer was purchased ,z Is the year of repair . It is required to find the minimum cost .

Ideas

set up dp[i] Before presentation i There is money needed for computers to be available every year , Put it first j A new computer was replaced in (1<=j<=i), Then the state transition equation is obtained

dp[i] = min(dp[j-1]+c+m[j][i]) (1<=j<=i)

Through this O(n^2) The answer can be obtained through the program of .

AC Code

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;
const int maxn = 1005;
int c, y;
int m[maxn][maxn];
int dp[maxn];

int main(void)
{
    
    while(~scanf("%d", &c)) {
    
        scanf("%d", &y);
        for(int i = 1; i <= y; ++i) {
    
            for(int j = i; j <= y; ++j) {
    
                scanf("%d", &m[i][j]);
            }
        }
        memset(dp, 0x3f, sizeof(dp));
        dp[0] = 0;
        for(int i = 1; i <= y; ++i) {
    
            for(int j = 1; j <= i; ++j) {
    
                dp[i] = min(dp[i], dp[j-1]+c+m[j][i]);
            }
        }
        printf("%d\n", dp[y]);
    }
    return 0;
}