【题意】
有n头牛在2*b的牧场上,只可以修建k(k<=n)个矩形牛棚,牛棚之间不能有重叠的部分,求牛棚的最小面积
【输入】
第一行n、k、b
【输出】
最小面积
状压dp
离散一下,用0~3表示这一列的状态
然后dp,f[i][j][k]表示第i列用了j个牛棚,状态为k的最小面积
k分为0~4,表示
0:什么也没有
1:上面一格被覆盖
2:下面一个被覆盖
3:两格被同一个矩形覆盖
4:两格被不同的矩形覆盖
program poj2430;
var
inf,tot,n,k,b,i,j:longint;
st,x,y,p:array [0..1001] of longint;
f:array [0..1001,0..1001,0..4] of longint;......
阅读全文