1. 首页
  2. Let's OI!
  3. 正文

bzoj1270[BeijingWc2008]雷涛的小猫【DP】

  • 内容
  • 评论
  • 相关

有段时间没有写了，NOIP就快来了，弄点DP题目做做吧。

【bzoj1270】[BeijingWc2008]雷涛的小猫
题目是权限题，不过NOI题库可以交。
很容易想到朴素DP方程：
设f[i,j]为前i棵树，高度为j时能得到的最多柿子数量，a[i,j]为第i棵树在高度j的柿子数量，那么：
f[i,j]=max(f[i,j+1],f[k,j+delta])+a[i,j]（1<=k<=n）
但这样弄是O(N^3)，可以发现f[k,j+delta]是固定的，当j+delta的高度的树DP完后就不会再变了，于是记录每一个高度的最大值就行。

代码：

var
  a,f:array[1..2000,1..2000]of longint;
  ma:array[1..2000]of longint;
  n,m,d,i,j,k,p,q:longint;
function max(a,b:longint):longint;
begin
  if a>b then exit(a) else exit(b);
end;
begin
  read(n,m,d);
  for i:=1 to n do
  begin
    read(p);
    for j:=1 to p do
    begin
      read(q);
      inc(a[i,q]);
    end;
  end;
  for i:=1 to n do
  begin
    f[i,m]:=a[i,m];
    ma[m]:=max(ma[m],a[i,m]);
  end;
  for j:=m-1 downto 1 do
  for i:=1 to n do
  begin
    f[i,j]:=f[i,j+1]+a[i,j];
    if j+d<=m then f[i,j]:=max(f[i,j],ma[j+d]+a[i,j]);
    ma[j]:=max(ma[j],f[i,j]);
  end;
  writeln(ma[1]);
end.

评论

0条评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。