HNOI 2004 敲磚塊

2019-11-09 20:30:20

字體：大中小

來源：轉載

供稿：網友

題目鏈接：點我點我:-) 題目描述：在一個凹槽中放置了 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個 f[i][j][k] $f[i][j][k]$ 表示第 i $i$ 列選了連續的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]$

感想：這樣水的題目不應該想不到，主要是被原圖弄混亂了，原圖會使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]); }