題目鏈接：點我點我:-) 題目描述： 在一個凹槽中放置了 n 層磚塊、最上面的一層有n 塊磚，從上到下每層依次減少一塊磚。每塊磚 都有一個分值，敲掉這塊磚就能得到相應的分值，如下圖所示。
14 15 4 3 23 33 33 76 2 2 13 11 22 23 31如果你想敲掉第 i 層的第j 塊磚的話，若i=1，你可以直接敲掉它；若i>1，則你必須先敲掉第 i-1 層的第j 和第j+1 塊磚。 你現在可以敲掉最多 m 塊磚，求得分最多能有多少。
輸入格式： 輸入文件的第一行為兩個正整數 n 和m；接下來n 行，描述這n 層磚塊上的分值a[i][j],滿足 0≤a[i][j]≤100。 對于 100%的數據，滿足1≤n≤50，1≤m≤n*(n+1)/2；
輸出格式： 輸出文件僅一行為一個正整數，表示被敲掉磚塊的最大價值總和。
思路： 將三角形左對齊如下：
14 15 4 3 2333 33 76 22 13 1122 2331可以發現，每一列需要選的是從最上面開始連續的若干個，若是k個，那么它右邊的那一列至少選了k-1個
感想： 這樣水的題目不應該想不到，主要是被原圖弄混亂了，原圖會使DP有后效性，轉移繁瑣，轉換一下就非常好做了，限制條件被巧妙地轉換了。 對于DP題，在后效性或有奇怪的問題時，應該學會轉換而消除原有干擾
代碼：
//miaomiao 2017.2.8 #include<cstdio> #include<algorithm> using namespace std; #define For(i, a, b) for(int i = (a); i <= (int)(b); i++) #define Forr(i, a, b) for(int i = (a); i >= (int)(b); i--) #define N (50+5) #define M (1500+5) int f[N][N][M], a[N][N], sum[N][N]; int main(){ int n, m, ans = 0; scanf("%d%d", &n, &m); For(i, 1, n) For(j, 1, n-i+1) scanf("%d", &a[i][j]); For(i, 1, n) For(j, 1, n-i+1) sum[i][j] = sum[i][j-1]+a[j][i]; f[n][1][1] = a[1][n]; Forr(i, n-1, 1) For(j, 0, n-i+1) For(k, 2*j-1, m){ if(k < 0) continue; For(x, max(j-1, 0), n) f[i][j][k] = max(f[i][j][k], f[i+1][x][k-j]); f[i][j][k] += sum[i][j]; if(i == 1) ans = max(ans, f[i][j][k]); }新聞熱點
疑難解答
