题目描述

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

输入输出格式

输入格式：

第一行为一个整数N，表示木块个数。

第二行是N个整数，表示N块木块的高度。

【数据规模】

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

输出格式：

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

输入输出样例

输入样例#1：

3

2 3 5

输出样例#1：

5

Solution

这道题想了我好一会啊,一直往状压方面凑...不过一开始忽略了一个条件,所有的木块都要放完.

状态需要联系到差值,这类要求相等的题目似乎都可以和差值联系上.

定义状态:

\[f[i][j]\]

1) i代表当前到了第 i 个木块,然后 j 代表此时较小值与较大值的差值.

2) f[i][j] 保存的是当前较小值的值.

状态转移

1) 一个基本的方向：我们让当前的较小值取更大,更接近较大值.

2) 当前这个木块有两个走向:

给较小值:

此时我们由前一个状态走过来话,他们的差值会变得更小.

同时这个较小值也会变大.

此时我们的状态转移即为:

\[f[i][j]=max(f[i-1][j],f[i-1][j+c[i]]+c[i]);\]

给较大值

此时同理上方,但是我们需要比较当前这个 j 和 c[i] 的大小.

因为我们 f 数组记录的是较小值.所以不可能之前的差值为负数.

此时状态转移为:

1.c[i] 大于 j

\[f[i][j]=max(f[i][j],f[i-1][c[i]-j]+c[i]-j);\]

2. j 小于 c[i]

\[f[i][j]=max(f[i][j],f[i-1][j-c[i]]);\]

于是我们转移便已完成.

不过这道题目还有一个坑点,就是极小值必须赋成很小.

否则会 WA 的很惨.

代码

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