7-5 小李打怪兽
分数 200
作者 陈科
单位 慈溪信息学学习中心
小李对故乡的思念全部化作了对雾霾天气的怨念，这引起了掌控雾霾的邪神的极大不满，邪神派去了一只小怪兽去对付小李，由于这只怪兽拥有极高的IQ，它觉得直接消灭小李太没有难度了，它决定要和小李在智力水平上一较高下。我们可否帮助小李来战胜强大的怪兽呢？

问题是这样的：给定一堆正整数，要求你分成两堆，两堆数的和分别为S1和S2，谁分的方案使得S1S1-S2S2的结果小（规定S1>=S2），谁就将获得胜利。

注：S2可以等于0

输入格式:
第一行n，表示共有n个数

第二行共n个用空格隔开的正整数ai，表示给定的一堆正整数。

输出格式:
输出就一个整数，表示S1S1-S2S2的最小值。

【样例说明】

1和4一堆，2和3一堆，55-55 = 0

【数据规模】

60%的数据，1<=n<=20

80%的数据，1<=n<=50，ai<=20

100%的数据，1<=n<=100，ai<=100

输入样例:
4
1 2 3 4
输出样例:
0
代码长度限制
16 KB
时间限制
1000 ms
内存限制
128 MB
栈限制
8192 KB

校赛自己的超时代码

#include<bits/stdc++.h>
using namespace std;

const int N = 105;

int n, sum;
int a[N];
int mi = 1e8 + 10;

void dfs(int u, int cur)
{
    if (u >= n + 1)
    {
        int sum1 = cur;
        int sum2 = sum - cur;
        mi = min(mi, abs(sum1 * sum1 - sum2 * sum2));
        return;
    }
    dfs(u + 1, cur + a[u]);
    dfs(u + 1, cur);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        sum += a[i];
    }
    dfs(1, 0);
    cout << mi << endl;
    return 0;
}

csdn上的讲解，发现是01背包问题
讲解：
如题意：要把n个数分成两份，这两份尽可能接近

也就是说其中一份大于等于总和的一半，另一份小于等于，

然后我们看小于等于的那一份，

就是说要在n个数里找出m（m未知）个数使其和小于等于sum/2、且最大，自然剩余n-m个数的和大于等于sum/2、且最小

这两部分就最接近了，

关键就是找这m个数了，

这就等价与n个物品，sum/2的背包（价值与重量相等）

本题的特殊之处在于：理解上面分析后发现，物品的价值和体积是一样的

#include<bits/stdc++.h>
using namespace std;

const int N = 105, M = 1e5 + 10;

int n, sum, m;
int w[N];
int f[N][5005];//总和的一半
//此处经过分析，可知每个物品的体积和价值相同
int dfs(int u, int spv)//返回u~n中总和小于spv 的最大和（考虑小的那一部分，此时尽可能最大，使得最后的差最小）
{
    if (f[u][spv]) return f[u][spv];
    if (u >= n + 1)
    {
        return 0;//根据返回值得出，后面没得选，所以返回0
    }

    int tmp = dfs(u + 1, spv);//不选
    if (spv >= w[u])
    {
        tmp = max(tmp, dfs(u + 1, spv - w[u]) + w[u]);
    }

    f[u][spv] = tmp;
    return tmp;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &w[i]);
        sum += w[i];
    }
    m = sum / 2;

    int sum1 = dfs(1, m);
    int sum2 = sum - sum1;
    cout << abs(sum1 * sum1 - sum2 * sum2) << endl;
    return 0;
}

优化成dp

#include<bits/stdc++.h>
using namespace std;

const int N = 105, M = 1e5 + 10;

int n, sum, m;
int w[N];
int f[N][5005];//总和的一半
////此处经过分析，可知每个物品的体积和价值相同
//int dfs(int u, int spv)//返回u~n中总和小于spv 的最大和（考虑小的那一部分，此时尽可能最大，使得最后的差最小）
//{
//  if (f[u][spv]) return f[u][spv];
//  if (u >= n + 1)
//  {
//      return 0;//根据返回值得出，后面没得选，所以返回0
//  }
//  
//  int tmp = dfs(u + 1, spv);//不选
//  if (spv >= w[u])
//  {
//      tmp = max(tmp, dfs(u + 1, spv - w[u]) + w[u]);
//  }
//
//  f[u][spv] = tmp;
//  return tmp;
//}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &w[i]);
        sum += w[i];
    }
    m = sum / 2;

    //注意遍历顺序
    for (int i = n; i >= 1; i--)
    {
        for (int j = 0; j <= m; j++)
        {
            f[i][j] = f[i + 1][j];
            if (j >= w[i])
            {
                f[i][j] = max(f[i][j], f[i + 1][j - w[i]] + w[i]);
            }
        }
    }
    int sum1 = f[1][m];
    int sum2 = sum - sum1;
    cout << abs(sum1 * sum1 - sum2 * sum2) << endl;
    return 0;
}

空间压缩

#include<bits/stdc++.h>
using namespace std;

const int N = 105, M = 1e5 + 10;

int n, sum, m;
int w[N];
int f[5005];//总和的一半


int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &w[i]);
        sum += w[i];
    }
    m = sum / 2;

    //注意遍历顺序
    for (int i = n; i >= 1; i--)
    {
        for (int j = m; j >= w[i]; j--)
        {
            //f[j] = f[j];
                f[j] = max(f[j], f[j - w[i]] + w[i]);
        }
    }
    int sum1 = f[m];
    int sum2 = sum - sum1;
    cout << abs(sum1 * sum1 - sum2 * sum2) << endl;
    return 0;
}