Light oj 1126 - Building Twin Towers(dp)_professor sofdor ali is fascinated about twin towe-程序员宅基地

技术标签： DP 动态规划

1126 - Building Twin Towers

PDF (English)

Statistics

Forum

Time Limit: 4 second(s)

Memory Limit: 32 MB

Professor Sofdor Ali is fascinated about twin towers. So, in this problem you are working as his assistant, and you have to help him making a large twin towers.

For this reason he gave you some rectangular bricks. You can pick some of the bricks and can put bricks on top of each other to build a tower. As the name says, you want to make two towers that have equal heights. And of course the height of the towers should be positive.

For example, suppose there are three bricks of heights 3, 4 and 7. So you can build two towers of height 7. One contains a single brick of height 7, and the other contains a brick of height 3 and a brick of height 4. If you are given bricks of heights 2, 2, 3 and 4 then you can make two towers with height 4 (just don't use brick with height 3).

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with an integer n (1 ≤ n ≤ 50), denoting the number of bricks. The next line contains n space separated integers, each containing the height of the brick h_i (1 ≤ h_i ≤ 500000). You can safely assume that the sum of heights of all bricks will not be greater than 500000.

Output

For each case, print the case number and the height of the tallest twin towers that can be built. If it's impossible to build the twin towers as stated, print "impossible".

Sample Input

Output for Sample Input

3 4 7

10 9 2

21 21

15 15 14 24 14 3 20 23 15

Case 1: 7

Case 2: impossible

Case 3: 21

Case 4: 64

PROBLEM SETTER: JANE ALAM JAN

dp[i][j] 代表前i个数形成差为j 的较大数的最大值

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>

#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(x,y) ((x+y)>>1)

#define bug printf("hihi\n")

#define eps 1e-12

typedef __int64 ll;

using namespace std;

#define INF 0x3f3f3f3f
#define N 500005

int dp[2][N];

int a[55];

int n;
int all;

void DP()
{
    int i,j;
    memset(dp,-1,sizeof(dp));
    dp[0][0]=0;
    int cur,to;
    cur=0;
    for(i=1;i<=n;i++)
      {
          int to=cur^1;
          memset(dp[to],-1,sizeof(dp[to]));

          for(int d=0;d+a[i]<=all;d++)
          {

              if(dp[cur][d]<0) continue;
              dp[to][d]=max(dp[to][d],dp[cur][d]);
              dp[to][d+a[i]]=max(dp[to][d+a[i]],dp[cur][d]+a[i]);

              if(d>=a[i])   dp[to][d-a[i]]=max(dp[to][d-a[i]],dp[cur][d]);
              else dp[to][a[i]-d]=max(dp[to][a[i]-d],dp[cur][d]+a[i]-d);
          }
          cur^=1;
      }
     if(dp[cur][0]<=0)
        printf("impossible\n");
     else
        printf("%d\n",dp[cur][0]);
}

int main()
{
    int i,j,t,ca=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        all=0;
        for(i=1;i<=n;i++)
            {
                scanf("%d",&a[i]);
                all+=a[i];
            }
        printf("Case %d: ",++ca);
        DP();
    }
    return 0;
}

/*

4
3
3 4 7
3
10 9 2
2
21 21
9
15 15 14 24 14 3 20 23 15

*/

本文链接：https://blog.csdn.net/u014737310/article/details/48733505

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

前端开发之vue-grid-layout的使用和实例-程序员宅基地

文章浏览阅读1.1w次，点赞7次，收藏34次。vue-grid-layout的使用、实例、遇到的问题和解决方案_vue-grid-layout

Power Apps-上传附件控件_powerapps点击按钮上传附件-程序员宅基地

文章浏览阅读218次。然后连接一个数据源，就会在下面自动产生一个添加附件的组件。把这个控件复制粘贴到页面里，就可以单独使用来上传了。插入一个“编辑”窗体。_powerapps点击按钮上传附件

C++ 面向对象（Object-Oriented）的特征 & 构造函数& 析构函数_"object(cnofd[\"ofdrender\"])十条"-程序员宅基地

文章浏览阅读264次。(1) Abstraction (抽象)(2) Polymorphism (多态)(3) Inheritance (继承)(4) Encapsulation (封装)_"object(cnofd[\"ofdrender\"])十条"

修改node_modules源码，并保存，使用patch-package打补丁，git提交代码后，所有人可以用到修改后的_修改 node_modules-程序员宅基地

文章浏览阅读133次。删除node_modules，重新npm install看是否成功。在 package.json 文件中的 scripts 中加入。修改你的第三方库的bug等。然后目录会多出一个目录文件。_修改 node_modules

【】kali--password:su的 Authentication failure问题，&sudo passwd root输入密码时Sorry, try again._password: su: authentication failure-程序员宅基地

文章浏览阅读883次。【代码】【】kali--password:su的 Authentication failure问题，&sudo passwd root输入密码时Sorry, try again._password: su: authentication failure

整理5个优秀的微信小程序开源项目_微信小程序开源模板-程序员宅基地

文章浏览阅读1w次，点赞13次，收藏97次。整理5个优秀的微信小程序开源项目。收集了微信小程序开发过程中会使用到的资料、问题以及第三方组件库。_微信小程序开源模板

随便推点

Centos7最简搭建NFS服务器_centos7 搭建nfs server-程序员宅基地

文章浏览阅读128次。Centos7最简搭建NFS服务器_centos7 搭建nfs server

Springboot整合Mybatis-Plus使用总结(mybatis 坑补充)_mybaitis-plus ruledataobjectattributemapper' and '-程序员宅基地

文章浏览阅读1.2k次，点赞2次，收藏3次。前言mybatis在持久层框架中还是比较火的，一般项目都是基于ssm。虽然mybatis可以直接在xml中通过SQL语句操作数据库，很是灵活。但正其操作都要通过SQL语句进行，就必须写大量的xml文件，很是麻烦。mybatis-plus就很好的解决了这个问题。..._mybaitis-plus ruledataobjectattributemapper' and 'com.picc.rule.management.d

EECE 1080C / Programming for ECESummer 2022 Laboratory 4: Global Functions Practice_eece1080c-程序员宅基地

文章浏览阅读325次。EECE 1080C / Programming for ECESummer 2022Laboratory 4: Global Functions PracticePlagiarism will not be tolerated:Topics covered:function creation and call statements (emphasis on global functions)Objective:To practice program development b_eece1080c

洛谷p4777 【模板】扩展中国剩余定理-程序员宅基地

文章浏览阅读53次。被同机房早就1年前就学过的东西我现在才学，wtcl。设要求的数为\(x\)。设当前处理到第\(k\)个同余式，设\(M = LCM ^ {k - 1} _ {i - 1}\) ，前\(k - 1\)个的通解就是\(x + i * M\)。那么其实第\(k\)个来说，其实就是求一个\(y\)使得\(x + y * M ≡ a_k(mod b_k)\)转化一下就是\(y * M ...

android 退出应用没有走ondestory方法,[Android基础论]为何Activity退出之后，系统没有调用onDestroy方法？...-程序员宅基地

文章浏览阅读1.3k次。首先，问题是如何出现的？晚上复查代码，发现一个activity没有调用自己的ondestroy方法我表示非常的费解，于是我检查了下代码。发现再finish代码之后接了如下代码finish();System.exit(0);//这就是罪魁祸首为什么这样写会出现问题System.exit(0);////看一下函数的原型public static void exit (int code)//Added ..._android 手动杀死app,activity不执行ondestroy

SylixOS快问快答_select函数导致堆栈溢出 sylixos-程序员宅基地

文章浏览阅读894次。Q: SylixOS 版权是什么形式, 是否分为<开发版税>和<运行时版税>.A: SylixOS 是开源并免费的操作系统, 支持 BSD/GPL 协议(GPL 版本暂未确定). 没有任何的运行时版税. 您可以用她来做任何您喜欢做的项目. 也可以修改 SylixOS 的源代码, 不需要支付任何费用. 当然笔者希望您可以将使用 SylixOS 开发的项目 (不需要开源)或对 SylixOS 源码的修改及时告知笔者.需要指出: SylixOS 本身仅是笔者用来提升自己水平而开发的_select函数导致堆栈溢出 sylixos