这个打砖头是很经典的题目。
一开始想着在题目给的形状上dp，结果发现这样的话会有三角形重合现象也就是动规有了后效性。
消除后效性要么转换状态，要么在状态里记录一下取数的情况。记录取数的情况，状压dp？别开玩笑了我直接搞不了。
那么只能转换一下，上网上看了别人的方法，把三角形倒过来了！
比如说样例：
2 2 3 4
8 2 7
2 3
49
倒过来之后——>
4
3 7
2 2 3
2 8 2 49
那么每一点只能由左边的点转移过来，和左上角一直到上一行末尾的数转移过来。
如第四行第2个数可以从第三行的1，2，3个数转移过来。为什么？再回去看看题吧……
那么就可以开状态f[i,j,k]表示取到i,j这个位置，取了k个数的最大得分。
那么如果取这个数，只能是a[i,1]+a[i,2]+...+a[i,j](这个预处理出来)+f[i-1,p,k-j] 其中p取j-1到i-1。如上述。
还应该注意每行都应该计算f[i,0,k]表示这一行不取数的答案。代码如下：
View Code var sum:array[0..50,0..50] of longint; a:array[0..50,0..50] of longint; ans,n,m:longint; i,j,k,p:longint; f:array[0..50,0..50,0..500] of longint;function max(a,b:Longint):longint;beginif a>b then exit(a) else exit(b);end;begin readln(n,m); ans:=0;for i:=1 to n dofor j:=1 to n-i+1 do read(a[n-j+1,i]);for i:=1 to n dofor j:=1 to i do sum[i,j]:=sum[i,j-1]+a[i,j]; fillchar(f,sizeof(f),$ff);for i:=0 to n do f[i,0,0]:=0; f[1,1,1]:=a[1,1];for i:=2 to n dofor j:=0 to i dofor k:=0 to m doif k>=j then beginfor p:=j-1 to i-1 doif f[i-1,p,k-j]>-1 then f[i,j,k]:=max(f[i,j,k],sum[i,j]+f[i-1,p,k-j]); ans:=max(ans,f[i,j,k]);end; writeln(ans); end.
转载于:https://www.cnblogs.com/zjerly/archive/2011/11/02/2232526.html
