| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 323 人关注过本帖
标题:jzxx4352 小李打怪兽
只看楼主 加入收藏
Jason_
Rank: 2
来 自:浙江台州
等 级:论坛游民
帖 子:38
专家分:46
注 册:2019-7-14
结帖率:50%
  问题点数:0  回复次数:4   
jzxx4352 小李打怪兽
题目描述
小李对故乡的思念全部化作了对雾霾天气的怨念,这引起了掌控雾霾的邪神的极大不满,邪神派去了
一只小怪兽去对付小李,由于这只怪兽拥有极高的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
搜索更多相关主题的帖子: 给定 表示 正整数 输入 输出 
【推荐】大型监控、工控、组态VC++./C#源码组件库2019下载!
【推荐】超50万数控、建模仿真、电力VC++/.NET图形源码库下载!
【推荐】专业CAD\GIS\业务流程VC++/C#可视化图形软件源码库下载!
2019-09-07 15:29
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:334
帖 子:6891
专家分:40054
注 册:2011-1-18
  得分:0 
题目要贴完整,比如
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]) );
}

2019-09-09 09:46
Jason_
Rank: 2
来 自:浙江台州
等 级:论坛游民
帖 子:38
专家分:46
注 册:2019-7-14
  得分:0 
回复 2楼 rjsp
好的,代码我试过了,可以AC的
2019-09-09 20:16
PandaHero
Rank: 3Rank: 3
等 级:论坛游民
威 望:7
帖 子:15
专家分:44
注 册:2016-3-29
  得分:0 
大神,好厉害
2019-09-09 22:16
wyx_luffy
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:3
帖 子:5
专家分:7
注 册:2019-11-14
  得分:0 
市赛题,以前刷到过
开代码:
程序代码:
#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];
}
2019-11-20 18:07
快速回复:jzxx4352 小李打怪兽
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.139459 second(s), 8 queries.
Copyright©2004-2019, BCCN.NET, All Rights Reserved