题目链接
洛谷 P1651 塔
思路分析
Task 1
考虑动态规划。我们定义 \(dp_{j,k}\) 表示当一塔高度为 \(j\)，另一塔高度为 \(k\) 能否搭出。那么 \(dp_{j,k}=dp_{j,k}\lor dp_{j-a_i,k}\lor dp_{k,j-a_i}\)，其中 \(i\) 枚举木块。但是根据题目要求这样写会 TLE+MLE，需要优化。
Task 2：差值 DP
观察到我们这样写只利用了下标，浪费了数组元素值这一存储数据的方法。我们考虑用元素值存储塔高，那么下标呢？由于我们只关注这两座塔是不是一样高，即高度差是否为 \(0\)，所以可以定义 \(dp_{i,j}\) 表示使用前 \(i\) 个木块，当两塔高度差为 \(j\) 时，较低的那座塔的高度。那么对于当前木块 \(i\)，分以下几种情况。
-
不用木块 \(i\)，\(dp_{i,j}=dp_{i-1,j}\)
-
用木块 \(i\)，放在低塔
- 若低塔仍为低塔，则高度差减少 \(a_i\)，低塔高度增加 \(a_i\)，所以 \(dp_{i,j}=dp_{i-1,j-a_i}+a_i\)
- 若低塔变成了高塔，则高度差就变为 \(a_i-j\)，低塔高度变为原高塔高度，增加了 \(j\)，即 \(dp_{i,j}=dp_{i-1,a_i-j}+j\)
所以 \(dp_{i,j}=dp_{i-1,|j-a_i|}+\min{(j,a_i)}\)。
-
用木块 \(i\)，放在高塔，则高度差增加 \(a_i\)，所以 \(dp_{i,j}=dp_{i-1,j+a_i}\)
综上，状态转移方程如下，其中 \(i,j\) 含义与定义相同，由题意一开始只有 \(dp_{0,0}\) 可以拼出，所以初始化为 \(0\)，其它则为一极小值。
\[dp_{i,j}=\min{(dp_{i-1,j},dp_{i-1,|j-a_i|}+\min(j,a_i),dp_{i-1,j+a_i})}
\]
代码见最下方，时空复杂度均为 \(O(n\sum{a_i})\)。
Task 3：滚动数组优化
发现 \(dp_{i,j}\) 的更新只与上一行的数据有关，所以可以进行优化，用两个数组记录本行和上一行的数据。代码略。
代码呈现
此处为 Task 2 代码。
#include<bits/stdc++.h>
using namespace std;const int N=55,M=500010;
int n,m;
int a[N],dp[N][M];int main(){scanf("%d",&n);for (int i=1;i<=n;++i) scanf("%d",a+i);for (int i=1;i<=n;++i) m+=a[i]; // a[i] 之和memset(dp,-0x3f,sizeof dp); // 注意初始化dp[0][0]=0;for (int i=1;i<=n;++i){for (int j=0;j<=m;++j)dp[i][j]=max({dp[i-1][j],dp[i-1][abs(j-a[i])]+min(j,a[i]),dp[i-1][j+a[i]]});}printf("%d",(dp[n][0]>0?dp[n][0]:-1));return 0;
}