编程论坛 → C++教室

jzxx4352 小李打怪兽

Jason_ 发布于 2019-09-07 15:29， 2767 次点击

题目描述
小李对故乡的思念全部化作了对雾霾天气的怨念，这引起了掌控雾霾的邪神的极大不满，邪神派去了
一只小怪兽去对付小李，由于这只怪兽拥有极高的IQ，它觉得直接消灭小李太没有难度了，它决定要和小
李在智力水平上一较高下。我们可否帮助小李来战胜强大的怪兽呢？
问题是这样的：给定一堆正整数，要求你分成两堆，两堆数的和分别为S1和S2，谁分的方案使得
S1*S1-S2*S2的结果小（规定S1>=S2），谁就将获得胜利。
注：S2可以等于0。

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

输出
输出就一个整数，表示 S1*S1-S2*S2 的最小值。

样例输入
4
1 2 3 4

样例输出
0

题目地址：http://oj.
密码是：beibao

4 回复

#2

rjsp2019-09-09 09:46

题目要贴完整，比如

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

程序代码：

#include <cstdio>

int main( void )
{
    unsigned n, a[100], s=0;
    scanf( "%u", &n );
    for( unsigned i=0; i!=n; ++i )
    {
        scanf( "%u", &a[i] );
        s += a[i];
    }

    unsigned dp[5001] = {};
    for( unsigned i=0; i!=n; ++i )
    {
        for( unsigned j=s/2; j>=a[i]; --j )
        {
            if( dp[j-a[i]]+a[i] > dp[j] )
                dp[j] = dp[j-a[i]]+a[i];
        }
    }
    printf( "%u\n", s*(s-2*dp[s/2]) );
}

#3

Jason_2019-09-09 20:16

回复 2楼 rjsp

好的，代码我试过了，可以AC的

#4

PandaHero2019-09-09 22:16

大神，好厉害

#5

wyx_luffy2019-11-20 18:07

市赛题，以前刷到过
开代码：

程序代码：

#include<iostream>
//#include<fstream>
using namespace std;
int main(){
    //ifstream cin("monster.in");
    //ofstream cout("monster.out");
    int dp[105]={0},n,a[105],tot,i,j,s1;
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>a[i];
        tot+=a[i];
    }
    for(i=1;i<=n;i++)
        for(j=tot/2;j>=a[i];j--){
            dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
        }
    s1=tot-dp[tot/2];
    cout<<s1*s1-dp[tot/2]*dp[tot/2];
}

1