題目大意：
給定一個(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)電腦，還是重新買第y+1臺(tái)電腦（注意，這里的y+1是指輸入中的第y+1行電腦，而不是指你已購(gòu)買了y+1臺(tái)電腦，因?yàn)閥年只能買輸入中的第y行電腦，為了不產(chǎn)生混淆，將電腦用編號(hào)表示）。顯然，某一階段的最優(yōu)解并不能一定導(dǎo)致全局的最優(yōu)解，所以肯定不能用貪心。
我們從最后的情況來(lái)考慮，最后必然是某一個(gè)編號(hào)為y的電腦，從第y年使用到第n年，而前面的1～y-1年，自己只可能購(gòu)買編號(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;
}