一类以差值作为状态的dp

概述

有一些给定高度的积木,来堆成两个高度相同的塔,问塔的最高高度。

dp[i][j] 表示前i块积木,两座塔高度相差为j,此时的最大高度

$$\begin{cases}
d[i+1][j+h[i+1]] = Max(d[i+1][j+h[i+1]],d[i][j]+h[i+1]) \; (放在较高的塔上) \\
d[i+1][j-h[i+1]] = Max(d[i+1][j-h[i+1]],d[i][j]-h[i+1]) \; (放在较低的塔上)
\end{cases}
$$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int h[maxn],sum[maxn],d[2][maxh];

sort(h+1,h+n+1);

sum[1] = h[1];
for(int i=2;i<=n;++i)
{
sum[i] = sum[i-1] + h[i];
}

memset(d[0],-INF,sum[n]*sizeof(d[0][0]));
d[0][0] = 0;

for(int i=1;i<=n;++i)
{
int t=i&1;
memset(d[t],-INF,sum[n]*sizeof(d[0][0]));

for(int j=0;j<=sum[i];++j)
{
d[t][j+b[i]] = max(d[t][j+b[i]],d[t^1][j]+b[i]);
d[t][abs(j-b[i])] = max(d[t][abs(j-b[i])],d[t^1][j]+b[i]);
d[t][j] = max(d[t][j],d[t^1][j]);
}
}

if(d[n&1][0]/2 <= 0) puts("-1");
else printf("%d\n",d[n&1][0]/2);

题目

ahu518

最基础的双塔dp,需要滚动数组优化

zoj3331

d[i][j]表示前i个块中,a塔与b塔高度差j的最低高度,这里高度差有可能为负

1
2
3
4
5
6
7
//a比b高时,j>0
d[i][j+a[i]] = max(d[i][j+a[i]],d[i-1][0+a[i]]+a[i]) //放到a上,注意b到a这段空闲不能跳过,所以从a,b等高开始加
d[i][j-b[i]] = max(d[i][j-b[i]],d[i-1][j-b[i]]+max(0,b[i]-j)) //放到b上,若b超过a时则增加高度

//b比a高时,j<0
d[i][j-b[i]] = max(d[i][j-b[i]],d[i-1][0-b[i]]+b[i]) //放到b上,注意b到a这段空闲不能跳过,所以从a,b等高开始加
d[i][j-b[i]] = max(d[i][j-b[i]],d[i-1][0-b[i]]+max(0,a[i]+j)) //放到a上,若a超过b时则增加高度

cf370-d

两个人初始分数为a,b
每轮现在两个人从$[-k,k]$中随机选一个数加入各自分数中
问t轮后a > b的方案数

初看是一个双塔dp,然而复杂度为$O(t^2k^2)$
但是由于k是连续的这个性质我们发现

$d[i][j] = d[i-1][j-2k] + 2d[i-1][j-2k+1] + \dots + (2k+1)d[i-1][j] + \dots d[i-1][j+2k]$

然后我们就可以处理出前缀和来做
从j-1转移到j,每次即减去前面一段和加上后面一段的前缀和

复杂度 $O(tk^2)$

不过也可以用生成函数+FFT做,复杂度$O(kt log(kt))$