P1651塔(动态规划)的最大高度计算方法

题目描述

小明很喜欢摆积木&＃xff0c;现在他正在玩的积木是由N个木块组成的&＃xff0c;他想用这些木块搭出两座高度相同的塔&＃xff0c;一座塔的高度是搭建它的所有木块的高度和&＃xff0c;并且一座塔至少要用一个木块。每个木块只能用一次&＃xff0c;也可以不用。目前已知每块木块的高度&＃xff0c;小明想知道在最终两个塔的高度相同的情况下&＃xff0c;他所能搭的塔的最大高度是多少&＃xff0c;你能帮助他吗&＃xff1f;

输入输出格式

输入格式&＃xff1a;

第一行为一个整数N&＃xff0c;表示木块个数。

第二行是N个整数&＃xff0c;表示N块木块的高度。

【数据规模】

对于100%的数据&＃xff0c;N≤50&＃xff0c;每块木块的高度h满足1≤h≤500000&＃xff0c;所有木块的高度总和≤500000。

输出格式&＃xff1a;

仅一个整数&＃xff0c;表示能搭建的塔的最大高度&＃xff0c;若不能搭建两座相同高度的塔&＃xff0c;则输出“-1”。

输入输出样例

输入样例#1&＃xff1a;

3
2 3 5

输出样例#1&＃xff1a;

5

Solution

这道题想了我好一会啊,一直往状压方面凑...不过一开始忽略了一个条件,所有的木块都要放完.
状态需要联系到差值,这类要求相等的题目似乎都可以和差值联系上.
定义状态:
\[f[i][j]\]
1) i代表当前到了第 i 个木块,然后 j 代表此时较小值与较大值的差值.
2) f[i][j] 保存的是当前较小值的值.

状态转移
1) 一个基本的方向&＃xff1a;我们让当前的较小值取更大,更接近较大值.
2) 当前这个木块有两个走向:
给较小值:
此时我们由前一个状态走过来话,他们的差值会变得更小.
同时这个较小值也会变大.
此时我们的状态转移即为:
\[f[i][j]&＃61;max(f[i-1][j],f[i-1][j&＃43;c[i]]&＃43;c[i]);\]
给较大值
此时同理上方,但是我们需要比较当前这个 j 和 c[i] 的大小.
因为我们 f 数组记录的是较小值.所以不可能之前的差值为负数.
此时状态转移为:
1.c[i] 大于 j
\[f[i][j]&＃61;max(f[i][j],f[i-1][c[i]-j]&＃43;c[i]-j);\]
2. j 小于 c[i]
\[f[i][j]&＃61;max(f[i][j],f[i-1][j-c[i]]);\]

于是我们转移便已完成.
不过这道题目还有一个坑点,就是极小值必须赋成很小.
否则会 WA 的很惨.

代码

#include
using namespace std;
const int inf&＃61;19260817;
const int maxn&＃61;51;
int f[maxn][maxn*10000],sum;
int n,c[maxn*2],ans&＃61;-1;
int main()
{ios::sync_with_stdio(false);cin>>n;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)cin>>c[i],c[i&＃43;n]&＃61;c[i],sum&＃43;&＃61;c[i];for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)for(int j&＃61;0;j<&＃61;sum;j&＃43;&＃43;)f[i][j]&＃61;-inf;f[1][0]&＃61;0,f[1][c[1]]&＃61;0;for(int i&＃61;2;i<&＃61;n;i&＃43;&＃43;)for(int j&＃61;0;j<&＃61;sum;j&＃43;&＃43;){f[i][j]&＃61;f[i-1][j];f[i][j]&＃61;max(f[i][j],f[i-1][j&＃43;c[i]]&＃43;c[i]);if(j}