題目鏈接：點我點我:-) 題目描述： 在一個凹槽中放置了 n 層磚塊、最上面的一層有n 塊磚，從上到下每層依次減少一塊磚。每塊磚 都有一個分值，敲掉這塊磚就能得到相應(yīng)的分值，如下圖所示。

如果你想敲掉第 i 層的第j 塊磚的話，若i=1，你可以直接敲掉它；若i>1，則你必須先敲掉第 i-1 層的第j 和第j+1 塊磚。 你現(xiàn)在可以敲掉最多 m 塊磚，求得分最多能有多少。

輸入格式： 輸入文件的第一行為兩個正整數(shù) n 和m；接下來n 行，描述這n 層磚塊上的分值a[i][j],滿足 0≤a[i][j]≤100。 對于 100%的數(shù)據(jù)，滿足1≤n≤50，1≤m≤n*(n+1)/2；

輸出格式： 輸出文件僅一行為一個正整數(shù)，表示被敲掉磚塊的最大價值總和。

思路： 將三角形左對齊如下：

可以發(fā)現(xiàn)，每一列需要選的是從最上面開始連續(xù)的若干個，若是k個，那么它右邊的那一列至少選了k-1個 f[i][j][k]$f[i][j][k]$ 表示第 i$i$ 列選了連續(xù)的j$j$個，且包括第 i+1$i+1$ 至 n$n$ 列一共選了k$k$個 方程很好推了： f[i][j][k]=Max(f[i][x][k?j])+∑jy=1a[y][i]$f[i][j][k] = Max(f[i][x][k-j]) + /sum_{y=1}^{j}a[y][i]$

感想： 這樣水的題目不應(yīng)該想不到，主要是被原圖弄混亂了，原圖會使DP有后效性，轉(zhuǎn)移繁瑣，轉(zhuǎn)換一下就非常好做了，限制條件被巧妙地轉(zhuǎn)換了。 對于DP題，在后效性或有奇怪的問題時，應(yīng)該學(xué)會轉(zhuǎn)換而消除原有干擾

代碼：