題目大意：

    給定一個(gè)時(shí)間期間n，電腦的價(jià)格c，以及電腦的維修費(fèi)用m(y,z)（第y臺(tái)電腦從y年用到第z年總的維修費(fèi)用）。讓你求出在期限n中使用電腦的最低費(fèi)用。

思路：
    為了讓總費(fèi)用最低，你必須作出這樣的決策：假設(shè)你正在使用某一臺(tái)電腦已用到y(tǒng)年，你y+1年是繼續(xù)用這臺(tái)電腦，還是重新買(mǎi)第y+1臺(tái)電腦（注意，這里的y+1是指輸入中的第y+1行電腦，而不是指你已購(gòu)買(mǎi)了y+1臺(tái)電腦，因?yàn)閥年只能買(mǎi)輸入中的第y行電腦，為了不產(chǎn)生混淆，將電腦用編號(hào)表示）。顯然，某一階段的最優(yōu)解并不能一定導(dǎo)致全局的最優(yōu)解，所以肯定不能用貪心。
    我們從最后的情況來(lái)考慮，最后必然是某一個(gè)編號(hào)為y的電腦，從第y年使用到第n年，而前面的1～y-1年，自己只可能購(gòu)買(mǎi)編號(hào)為1~y-1的電腦使用到y(tǒng)-1年。這樣，問(wèn)題的范圍就減小了，從編號(hào)為1～n的電腦使用n年，降低到了編號(hào)為1～y-1的電腦使用y-1年。經(jīng)分析，可推出遞推式：
    F[n] = min { F[i] + c + m[i+1][n] | 0<=i<=n-1 }
F[n]表示n臺(tái)電腦使用n年的最低費(fèi)用

代碼：

#include <cstdio>
#include <climits>
#include <cstring>

const int MAX = 1005;
int n, c;
int mend[MAX][MAX];
int f[MAX];
int cost;

bool Input ()
{
    if ( scanf("%d", &c) == EOF )
        return false;
    scanf("%d", &n);
    int i, j;
    for (i=1; i<=n; i++)
    {
        for (j=i; j<=n; j++)
            scanf("%d", &mend[i][j]);
    }
    return true;
}


void Solve ()
{
    int i, j;
    memset(f, 0, sizeof(f));
    for (i=1; i<=n; i++)
    {
        f[i] = INT_MAX;
        for (j=0; j<i; j++)
        {
            if ( f[j] + mend[j+1][i] + c < f[i] )
                f[i] = f[j] + mend[j+1][i] + c;
        }
    }
    printf("%d\n", f[n]);
}

int main ()
{
    while ( Input() )
    {
        Solve ();
    }

    return 0;
}