堆砖块__牛客网

JacobGo！

package go.jacob.day915;

import java.util.Scanner;

public class Demo5 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] height = new int[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            height[i] = sc.nextInt();
            sum += height[i];
        }
        // dp0与dp1都表示低塔高度，dp0为上一轮，dp1为当前轮次
        // 长度设为2*sum+1，是因为高度差的范围是-sum到sum
        int[] dp0 = new int[2 * sum + 1];
        int[] dp1 = new int[2 * sum + 1];
        // 初始化
        for (int i = 0; i <= 2 * sum; i++)
            dp0[i] = -1;// 初始化为-1表示不存在该情况
        dp0[sum] = 0;

        for (int i = 0; i < n; i++) {
            int high = height[i]; 
            // 把j定义为（B堆高度-A堆高度）+sum; //
            // 范围从[-sum,sum]变为[0,sum*2];加上sum是为了方便用数组表示
            for (int j = 0; j <= 2 * sum; j++) {
                dp1[j] = dp0[j]; 
                // 放在A堆上
                if (j >= high && dp0[j - high] != -1) {
                    dp1[j] = Math.max(dp1[j], dp0[j - height[i]]);
                } 
                // 放在B堆上，B堆高度增大
                if (j + high <= 2 * sum && dp0[j + high] != -1) {
                    dp1[j] = Math.max(dp1[j], dp0[j + high]+high);
                }
            }
            //交换数组，保证每一轮循环dp0为上一轮数组
            int[] s = dp0;
            dp0 = dp1;
            dp1 = s;
        }

        
        if (dp0[sum] == 0)
            System.out.println(-1);
        else
            System.out.println(dp0[sum]);
        sc.close();

    }
}

发表于 2017-09-16 11:17:16 回复(0)

☠

### 分析

不知道怎么搞，看到题目保证答案不大于500000，想想这不是在提示我们“暴力搞没问题，我数据不大”么。于是我就就暴力搜索，枚举两堆塔的高度，但是需要一些剪枝：

1. 当其中一堆高度大于500000,可以剪掉;

2. 当较低的堆+剩下的砖块<较高的堆时，可以剪掉;

3. 当当前可能达到的最大高度小于已经发现最大高度时，可以剪掉;

### 我的答案

```cpp

#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 500000
int height[52];
int sum[52];
int n;
int ans=0;
void dfs(int n,int sum1,int sum2){
    if(sum1==sum2)
        ans=max(ans,sum1);
    if(n==0)
        return;
    if(sum1>MAX)
        return;
    if(sum1+sum[n]<sum2)
        return;
    if((sum1+sum2+sum[n])<=ans*2)
        return;
    dfs(n-1,min(sum1+height[n],sum2),max(sum1+height[n],sum2));
    dfs(n-1,min(sum2+height[n],sum1),max(sum2+height[n],sum1));
    dfs(n-1,sum1,sum2);
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>height[i];
    sort(height+1,height+n+1);
    for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]+height[i];
    dfs(n,0,0);
    cout<<(ans?ans:-1)<<endl;
}

```

https://blog.mythsman.com/2017/03/31/1/#堆砖块

发表于 2017-03-31 13:16:37 回复(0)

Java

拼多多幸运内推

@JacobGo！@minnnng@chorus 这三位的状态转移表述都是错的，虽然本题中不影响结果，但是不利于理解。

以下是正确表述

dp[j]表示B-A+sum为j时，B堆的最大高度

所以把砖块放在B堆时:dp1[j]=dp0[j-h]+h

A堆:dp1[j]=dp0[j+h]

不放：dp1[j]=dp0[j]

这才是正确状态转移，三位互相借鉴的时候就不能仔细看一遍？？

自己的代码分明是将A-B+sum作为j，为何注释里要说成B-A+sum，误人子弟。

以下是我的代码

import java.util.Arrays; 
import java.util.Scanner; 
public class Main{ public static void main(String[] args) {
    Scanner scan=new Scanner(System.in); 
    int n=scan.nextInt(); 
    int[] heights=new int[n]; 
    int count=0; 
    for(int i=0;i;i++){
        heights[i]=scan.nextInt(); 
        count+=heights[i]; 
    } 
    int[] dp1=new int[2*count+1]; 
    int[] dp0=new int[2*count+1]; 
    for(int i=0;i2*count+1;i++){
        dp0[i]=-1; 
    }
    dp0[count]=0; 
    for(int i=1;i1;i++){ 
         int height=heights[i-1]; 
         for(int j=0;j2*count+1;j++){
             dp1[j]=dp0[j]; 
             if(j-height>=0&&dp0[j-height]!=-1){
                 dp1[j]=Math.max(dp1[j],dp0[j-height]+height); 
             }             
             if(j+height2*count&&dp0[j+height]!=-1){
                 dp1[j]=Math.max(dp1[j],dp0[j+height]); 
             }
         } 
         for(int j=0;j2*count+1;j++){
             dp0[j]=dp1[j]; 
         }
     } 
     int max=-1; 
     for(int i=1;i1;i++){
        max=Math.max(max,dp0[count]); 
     }
     System.out.println(max==0?-1:max); 
     }
}

编辑于 2018-04-06 21:14:24 回复(0)

minnnng

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

int main() {
    int n = 0;
    cin >> n;
    vector<int> ts(n);
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> ts[i];
        sum += ts[i];
    }
    vector<vector<int>> dp(2, vector<int>(2*sum+1, -1));
    dp[0][sum] = 0;
    vector<int>* dp0 = &(dp[0]);
    vector<int>* dp1 = &(dp[1]);
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= 2*sum; ++j) {
            int h = ts[i-1];
            (*dp1)[j] = (*dp0)[j];
            if (j - h >= 0 && (*dp0)[j-h] != -1) {
                (*dp1)[j] = max((*dp1)[j], (*dp0)[j-h]);
            }
            if (j + h <= 2*sum && (*dp0)[j+h] != -1) {
                (*dp1)[j] = max((*dp1)[j], (*dp0)[j+h] + h);
            }
        }
        auto tmp = dp0;
        dp0 = dp1;
        dp1 = tmp;
    }
    if ((*dp0)[sum] == 0)
        cout << -1 << endl;
    else
        cout << (*dp0)[sum] << endl;
    return 0;
}
/*假设砖块分为A，B两堆，dp[i][j]中的j表示B-A的长度。
因为B-A有可能是负的，所以j整体偏移sum个长度，即2*sum+1。
而dp[i][j]的值则表示当A-B的值为j时，B的最大长度是多少。
dp[i][j] = dp[i-1][j]表示我不用第i块砖
dp[i][j] = max(dp[i-1][j-h], dp[i-1][j])表示我把砖放在A堆。
dp[i][j] = max(dp[i-1][j+h]+h, dp[i-1][j])表示我把砖放在B堆。
然后会爆内存，所以用了滚动数组。*/

发表于 2017-03-30 22:23:48 回复(13)

为啥要起名字

class Solution:
    def __init__(self):
        self.max_height=500000
        self.height=0
    def get_max_height(self,n,heights):
        heights.sort()
        sums=[0]*n
        sums[0]=heights[0]
        for i in range(1,n):
                sums[i]=sums[i-1]+heights[i]
        self.process(n-1,0,0,sums,heights)
        if not self.height:
            print(-1)
        else:
            print(self.height)
    def process(self,n,low,high,sums,heights):
        if low==high:
            self.height=max(low,self.height)
        if n<0:
            return
        #当其中高的那堆高度大于500000，剪掉（题目要求保证答案不大于500000）        if high>self.max_height:
            return
        #当矮的那堆加上剩下的砖块还是小于高的那堆，剪掉
        if low+sums[n]<high:
            return
        #当当前可能达到的最大高度小于已经发现的最大高度，剪掉
        if low+high+sums[n]<=self.height*2:
            return
        #砖块放到矮的那堆，这是高矮就得进行判断了，所以有min和max
        self.process(n-1,min(low+heights[n],high),max(low+heights[n],high),sums,heights)
        #砖块放到高的那堆
        self.process(n-1,low,high+heights[n],sums,heights)
        #砖块丢弃不放
        self.process(n-1,low,high,sums,heights)
if __name__=='__main__':
    n=int(raw_input())
    heights=list(map(int,raw_input().strip().split()))
    s=Solution()
    s.get_max_height(n,heights)

编辑于 2018-07-27 15:18:51 回复(0)

Java

牛客2793674号

/*
                 动态规划解决。(用砖堆两个塔，A塔和B塔,B塔-A塔高度差为: -sumHeight~sumHeight，防止数组下表越界，加上sumHeight)。

	 dp[i][j]表示使用前 i 块砖，B-A 塔高度差为 j 时 B 塔的最大高度。  则解为  dp[n][0].使用滚动数组方法解决当 n 过大时 dp[n+1][2*sumHeight+1]二维数组占用内存过高问题,状态转移方程为:

	  					dp[i-1][j], 第 i 块砖不用

	 dp[i][j] =  max    dp[i-1][j-height[i]], 第 i 块砖放在 A 塔

	   					dp[i-1][j+height[i]] + height[i], 第 i 块砖放在 B 塔


	


	*/
import java.util.*;
public class PileOfBricks {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		while(scan.hasNext()){
			int n = scan.nextInt();
			int[] height = new int[n+1];
			int sumHeight = 0;
			for(int i=1; i<=n ;i++){
				height[i] = scan.nextInt();
				sumHeight += height[i];
			}
			
			int[][] dp = new int[2][2*sumHeight+1];
			
			for(int i=0; i<2*sumHeight+1; i++)
				dp[0][i] = -1;
			
			dp[0][sumHeight] = 0;
			
			for(int i=1; i<=n; i++){
				for(int j=0; j<2*sumHeight+1; j++){
					dp[1][j] = dp[0][j];
					if(j-height[i]>=0 && dp[0][j-height[i]]!=-1)
						dp[1][j] = Math.max(dp[1][j], dp[0][j-height[i]]);
					if(j+height[i]<=2*sumHeight && dp[0][j+height[i]]!=-1)
						dp[1][j] = Math.max(dp[1][j], dp[0][j+height[i]]+height[i]);
				}
				int[] temp = dp[0];
				dp[0] = dp[1];
				dp[1] = temp;
			}
			if(dp[0][sumHeight] == 0)
				System.out.println(-1);
			else
				System.out.println(dp[0][sumHeight]);
		}
	}

}

编辑于 2017-08-01 11:14:51 回复(0)

潇潇古月

/**
思路来自于csdn上，大概看了一次，这次是完全凭记忆写出来的，主要的就是利用动态规划的思想，
dp[i][j]表示在使用前i块砖，高度差为j时低塔的高度，考虑四种情况：
1. 新砖块放在低塔上，低塔依然是低塔，即：
    dp[i][j] = dp[i-1][j+high] + high;
2. 新砖块放在低塔上，低塔变成了高塔，即：
    dp[i][j] = dp[i-1][high-j] + high-j;
3. 新砖块放在高塔上，高塔只可能是高塔，即：
    dp[i][j] = dp[i-1][j-high];
4. 放弃新砖块，不放在任何一个塔上，即：
    dp[i][j] = dp[i-1][j];
最终dp[i][j]取以上四种情况的最大值即可；
如果直接定义n*sum维的数组，内存会不够，所以优化了一下内存，应该有更好的方法，再学习了
*/
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] h = new int[n];
            int sum = 0;
            for (int i = 0; i < n; i++) {
                h[i] = sc.nextInt();
                sum += h[i];
            }
            int[][] dp = new int[2][sum+1]; //dp[i][j]表示前i个砖块中，堆成的塔，高度差为j时，低塔的最高高度
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < sum + 1; j++) {
                    dp[i][j] = Integer.MIN_VALUE;  //初始化为负无穷，表示没有这种高度的堆法
                }
            }
            dp[0][0] = 0;   //如果没有放砖的时候，低塔为0，高度差为0
            for (int i = 1; i <= n; i++) {
                int high = h[i-1];
                for (int j = 0; j <= sum; j++) {
                    if(j > high) {
                        //如果将砖块放在高塔上，则低塔高度不变，高度差增加
                        dp[1][j] = Math.max(dp[1][j], dp[0][j - high]);
                    } else {
                        //如果将砖块放在低塔上，低塔变高塔，高塔高度变低塔高度，高度差改变
                        dp[1][j] = Math.max(dp[1][j], dp[0][high - j] + (high - j));
                    }

                    //如果将新砖块放在低塔上，并且依然是低塔，则低塔高度增加
                    if(j + high <= sum)
                        dp[1][j] = Math.max(dp[1][j], dp[0][j + high] + high);

                    //放弃该砖块，不放在任何一个塔上
                    dp[1][j] = Math.max(dp[1][j], dp[0][j]);
                }
                System.arraycopy(dp[1], 0, dp[0], 0, sum + 1);
                for (int j = 0; j <= sum; j++) {
                    dp[1][0] = Integer.MIN_VALUE;
                }
            }
            if(dp[0][0] > 0)
                System.out.println(dp[0][0]);
            else
                System.out.println(-1);
        }
    }
}

编辑于 2017-07-28 12:51:19 回复(2)

chorus

借鉴前面几位大神的代码，分析都写在代码中

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] h = new int[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            h[i] = in.nextInt();
            sum += h[i];
        }
        //本来想用二维数组来存放，但运行会超出内存，所以行不通
        int[] dp0 = new int[sum * 2 + 1], dp1 = new int[sum * 2 + 1];
        //dp0表示上次放砖时各个位置的情况，dp1表示这次放砖时应该变成的情况
        //dp平移sum位是因为B堆-A堆高度的范围在-sum至sum之间，所以平移sum位以便存储每个的值
        //所以也就是说j下标为sum时表示A、B堆高度相同时的情况，往左就是B堆较高的情况，往右就是A堆较高的情况
        for (int i = 0; i < sum*2 + 1; i++) dp0[i] = -1;
        dp0[sum] = 0;
        for (int i = 1; i <= n; i++) {
            int hg = h[i-1];
            //j表示B堆-A堆的高度差（由于平移的原因，sum即为0，往左一次加1，往右依次减1）
            //dp1[j]存放的值表示B目前所能存放的最大高度
            //dp1[j]是在上次的基础上（也就是dp0）进行变换的
            for (int j = 0; j < 2 * sum + 1; j++) {
                dp1[j] = dp0[j];
                if (j - hg >= 0 && dp0[j - hg] != -1) {  
                    dp1[j] = Math.max(dp0[j - hg], dp1[j]);
                }
                if (j + hg <= 2 * sum && dp0[j + hg] != -1) {
                    dp1[j] = Math.max(dp0[j + hg] + hg, dp1[j]);
                }
            }
            //交换两个数组，确保dp0一直是上次的状态
            int[] t = dp0;
            dp0 = dp1;
            dp1 = t;
        }
        //最后一次变换完为dp0，所以对dp0进行求解
        if (dp0[sum] == 0) System.out.println(-1);
        else System.out.println(dp0[sum]);
    }
}

编辑于 2017-07-20 17:33:54 回复(2)

resolvewang

# 主要实现参考　https://blog.mythsman.com/2017/03/31/1/#堆砖块
# 在想不出来动态规划实现方法的时候，优化递归也是一个不错的选择

import sys

class Solution:
    def __init__(self):
        self.max_height = 500000
        self.height = 0

    def get_max_height(self, n, heights):
        # 排序过后从最高的砖块开始拿
        heights.sort()
        sums = [0] * len(heights)
        # 预处理数组，得到从矮到高砖块的累加和
        for i in range(len(heights)):
            if i == 0:
                sums[i] = heights[0]
            else:
                sums[i] = sums[i-1] + heights[i]
        self.process(n-1, 0, 0, sums, heights)
        if not self.height:
            print(-1)
        else:
            print(self.height)

    def process(self, n, low, high, sums, heights):
        if low == high:
            self.height = max([low, self.height])

        # 剪枝过程参考　https://blog.mythsman.com/2017/03/31/1/#堆砖块
        # 递归完成
        if n < 0:
            return
        # 高的一边比题目限制更大
        if high > self.max_height:
            return
        # 矮的加剩下的比高的小
        if low+sums[n] < high:
            return
        # 高的和矮的加剩下的不大于已知的方案
        if low+high+sums[n] <= self.height*2:
            return

        # 砖块放矮的一边，注意加了一块砖之后AB塔高矮可能发生变化
        self.process(n - 1, min([low+heights[n], high]), max([low+heights[n], high]), sums, heights)
        # 砖块如果放高的一边或者丢弃，那么AB塔相对高矮程度不会变化
        self.process(n - 1, low, high+heights[n], sums, heights)
        self.process(n - 1, low, high, sums, heights)


if __name__ == '__main__':
    total = int(sys.stdin.readline().strip())
    args = list(map(int, sys.stdin.readline().strip().split()))
    s = Solution()
    s.get_max_height(total, args)

编辑于 2018-07-12 19:54:01 回复(0)

古典文化

C++:

#include<iostream>
#include<vector>
#include <cstring>
#include<algorithm>
using namespace std;

int main(){
	int n;
	while (cin >> n){
		vector<int> height(n, 0);
		int sum = 0;
		for (int i = 0; i < n; i++){
			cin >> height[i];
			sum += height[i];
		}
		vector<vector<int>> dp(2, vector<int>(sum + 1, -1));
		dp[0][0] = 0;
		for (int i = 1; i <= n; i++){
			for (int j = 0; j <= sum; j++){
				int high = height[i - 1];
				dp[i & 1][j] = dp[(i - 1) & 1][j]; //不加砖块
				if (j + high <= sum && dp[(i - 1) & 1][j + high] >= 0)    //加到矮的那堆，比原来高的那堆矮
					dp[i & 1][j] = max(dp[i & 1][j], dp[(i - 1) & 1][j + high] + high);
				if (high - j >= 0 && dp[(i - 1) & 1][high - j] >= 0)     //加到矮的那堆，比原来高的那堆高
						dp[i & 1][j] = max(dp[i & 1][j], dp[(i - 1) & 1][high - j] + high - j);
				if (j - high >= 0 && dp[(i - 1) & 1][j - high] >= 0)        //加到高的那堆上
					dp[i & 1][j] = max(dp[i & 1][j], dp[(i - 1) & 1][j - high]);
			}
		}
		if (dp[n & 1][0] == 0)
			cout << -1 << endl;
		else
			cout << dp[n & 1][0] << endl;
	}
	return 0;
}

java:

import java.util.*;
public class Main{
	static int count = 0;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while(in.hasNext()){
			int n = in.nextInt();
			int[] height = new int[n];
			int sum = 0;
			for (int i = 0; i < n; i++) {
				height[i] = in.nextInt();
				sum += height[i];
			} 
			int[][] dp = new int[2][sum + 1];
			for(int j = 1; j < sum + 1; j++){
				dp[0][j] = -1;
			}
			for(int i = 1; i <=  n; i++){
				for (int j = 0; j <= sum; j++){
					int high = height[i - 1];
					dp[i & 1][j] = dp[(i - 1) & 1][j]; //不加砖块
					if (j + high <= sum && dp[(i - 1) & 1][j + high] >= 0)    //加到矮的那堆，比原来高的那堆矮
						dp[i & 1][j] = max(dp[i & 1][j], dp[(i - 1) & 1][j + high] + high);
					if (high - j >= 0 && dp[(i - 1) & 1][high - j] >= 0)     //加到矮的那堆，比原来高的那堆高
							dp[i & 1][j] = max(dp[i & 1][j], dp[(i - 1) & 1][high - j] + high - j);
					if (j - high >= 0 && dp[(i - 1) & 1][j - high] >= 0)        //加到高的那堆上
						dp[i & 1][j] = max(dp[i & 1][j], dp[(i - 1) & 1][j - high]);
				}
			}
			if (dp[n & 1][0] == 0)
				System.out.println(-1);
			else
				System.out.println(dp[n & 1][0]);
		}
		in.close();
	}
}

发表于 2017-06-26 22:41:22 回复(0)

张瑞泽

看懂了@minnnng 的答案，然后自己写了一波，里面有一些小的细节在注释里提了下，希望有帮助：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] value = new int[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            value[i] = in.nextInt();
            sum += value[i];
        }
        int[] dp0 = new int[sum * 2 + 1], dp1 = new int[sum * 2 + 1];
        /*
        i=0时，需要dp[-1][j]的状态，也就是不用任何硬币，sumA=0,sumB=0，sumA-sumB=0,故dp0[0+sum]=sumB=0
        其他sumA-sumB的情况是不能凑到的，比如dp[0][-1+sum]，sumB若取了0代表sumA=-1，这是不科学的。
        所以其他情况均赋值-1。
        dp1不需要赋值-1是因为在循环中会先给dp1[j]赋值dp0[j]的值。
        */
        for (int i = 0; i < dp0.length; i++) dp0[i] = -1;
        dp0[sum] = 0;
        for (int i = 1; i <= n; i++) {
            int v = value[i-1];
            for (int j = 0; j < 2 * sum + 1; j++) {
                dp1[j] = dp0[j];
                if (j - v >= 0 && dp0[j - v] != -1) {  dp1[j] = Math.max(dp0[j - v], dp1[j]);
                }
                if (j + v <= 2 * sum && dp0[j + v] != -1) {
                    dp1[j] = Math.max(dp0[j + v] + v, dp1[j]);
                }
            }
            //交换dp，让dp0始终代表dp[i-1][j]的状态。
            int[] temp = dp1;
            dp1 = dp0;
            dp0 = temp;
        }
        //因为最后会再将dp1交换到dp0上，所以输出时使用dp0。如果最后dp0[sum]=0的话，说明sumB=0，即没法凑到，则输出-1
        if (dp0[sum] == 0) System.out.println(-1);
        else System.out.println(dp0[sum]);
    }
}

补充=========================

@我的兄弟叫卷分享了一个算法，可以用更少的存储空间，以及更少的循环次数（需要结合滚动数组）。使得上面代码的dp0和dp1长度只需sum+maxHeight，即可。同理循环中j的次数也会减少。

参考如下：

http://www.cnblogs.com/hyfer/p/5791420.html

http://blog.csdn.net/ctxdecs/article/details/25882407

我暂时还没成功用此算法通过所有测试用例。。orz..

编辑于 2017-03-31 15:33:03 回复(0)

牛客558275203号

Python3，两种思路：动态规划和优化递归

n = int(input())
h = [int(i) for i in input().split()]
 
 
# 优化递归，通过100%，思路参考 @为啥要起名字
h.sort(reverse=True)
cumsum = [h[-1]]
for i in range(n-2, -1, -1):
    cumsum.append(cumsum[-1] + h[i])
cumsum = cumsum[::-1]
ans = 0

def solve(low, high, i):
    global ans
    if low == high:
        ans = max(ans, low)
    if i >= n:
        return
    if low + cumsum[i] < high:
        return
    if low + high + cumsum[i] <= ans*2:
        return
    if high > 500000:
        return
    solve(min(low+h[i], high), max(low+h[i], high), i+1)
    solve(min(low, high+h[i]), max(low, high+h[i]), i+1)
    solve(low, high, i+1)
    return

solve(0, 0, 0)
print(ans > 0 and ans&nbs***bsp;-1)
# 动态规划，TLE，通过30%，思路参考 @潇潇古月
'''
maxh = sum(h) // 2
dp = [0] + [-1] * maxh

for i in range(len(h)):
    temp = []
    for j in range(maxh+1):
        x = max(dp[j], dp[j-h[i]])
        if j + h[i] <= maxh and dp[j+h[i]] != -1:   
            x = max(x, dp[j+h[i]] + h[i])
        if dp[h[i]-j] != -1:   
            x = max(x, dp[h[i]-j] + h[i] - j)
        temp.append(x)
    dp = temp
    
print(dp[0] > 0 and dp[0]&nbs***bsp;-1)
'''

编辑于 2020-04-07 21:04:06 回复(0)

哟，我喜欢

dp[i] 表示两塔相差i时矮塔的高度

发表于 2019-07-19 22:51:50 回复(0)

我是一只小熊

#include <stdio.h>
#include <stdlib.h>
int a[60];
int d[500005];
int d1[500005];
#define NOF -1000000000
int main()
{
int n;
int i,j;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
d[0]=0;
for(i=1;i<=500000;i++)
d[i]=NOF;
for(i=1;i<=n;i++)
{
for(j=0;j<=500000;j++)
{
d1[j]=d[j];
if(j+a[i]<=500000)
{
if((d[j+a[i]])+a[i]>d1[j])
d1[j]=(d[j+a[i]])+a[i];
}
if(a[i]-j>=0)
{
if(d[a[i]-j]+a[i]-j>d1[j])
d1[j]=d[a[i]-j]+a[i]-j;
}
if(j-a[i]>=0)
{
if(d[j-a[i]]>d1[j])
d1[j]=d[j-a[i]];
}
}
for(j=0;j<=500000;j++)
d[j]=d1[j];
}
if(d[0]!=0)
printf("%d\n",d[0]);
else
printf("-1\n");

}
return 0;
}

C语言的写法

发表于 2018-09-06 10:40:41 回复(0)

逗比请来的猴子

import java.util.Arrays;
import java.util.Scanner;

/*
 * 参考大神解题思路：https://blog.mythsman.com/2017/03/31/1/
 * 题目给定了限制塔高最大为500000，网上其他的大神提供了使用dp的方法，但是看了半天没有看懂，想算了吧，如果真的遇到这种难度的，只能认栽；
 * 不过强行的暴力求解还是可以想到的，然后针对一些情况进行剪支处理
 * 1.塔高大于500000；
 * 2.较小的塔高加上剩下的所有砖块高度小于另一堆塔高的情况；
 * 3.两个塔高之和加上剩下所有砖块的所有高度之和小于已知最大的高度
 * */
public class Main {
    private static final int MAX_HEIGHT = 500000;
    private static int maxHeight = 0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int[] height = new int[n];
            int[] sum = new int[n];
            maxHeight = 0;
            height[0] = scanner.nextInt();
            for (int i = 1; i < n; i++) {
                height[i] = scanner.nextInt();
            }
            Arrays.sort(height);
            sum[0] = height[0];
            for (int i = 1; i < n; i++) {
                sum[i] = sum[i - 1] + height[i];
            }
            dfs(n - 1, sum, height, 0, 0);
            System.out.println(maxHeight == 0 ? -1 : maxHeight);
        }
    }

    private static void dfs(int n, int[] sum, int[] height, int sum1, int sum2) {
        if (sum1 == sum2) {
            maxHeight = Math.max(maxHeight, sum1);
        }
//        对应三种剪枝策略，大于最大的规定塔高、矮的塔高加上剩下所有砖高度之和小于另一塔高、任意一个塔高加上剩下的砖块之后小于已有相等高度
        if (n < 0 || sum1 > MAX_HEIGHT || sum1 + sum[n] < sum2 || sum1 + sum2 + sum[n] <= 2 * maxHeight) {
            return;
        }
//        将该砖放在A塔还是B塔上或者不放
        dfs(n - 1, sum, height, Math.min(sum1 + height[n], sum2), Math.max(sum1 + height[n], sum2));
        dfs(n - 1, sum, height, Math.min(sum2 + height[n], sum1), Math.max(sum2 + height[n], sum1));
        dfs(n - 1, sum, height, sum1, sum2);
    }
}

发表于 2018-04-11 20:41:55 回复(0)

DDUP4

/*

看了很多答案，也跑了他们的答案，很多答案都能AC，下面是我看了很多资料，然后在网上发现的另外一种解法，完全遍历了解空间、但不使用滚动数组，能AC

*/

import java.util.Arrays;

import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int N=in.nextInt();
int H[]=new int[N+1];
int sum=0;
for(int i=1;i<N+1;i++){
H[i]=in.nextInt();
sum+=H[i];
}
Arrays.sort(H);
int halfHeight=sum/2;
for(int i=N;i>=0;i--)
if(H[i]>halfHeight){
sum-=H[i];
H[i]=0;
halfHeight=sum/2;
}else
break;

int[][] res=new int[N+1][2*halfHeight+1];//res[i][j]的值为放置第i块砖后A堆的高度，j为B对A的高度差，j向正轴偏移halfHeight个长度,因为如果A与B的高度差超过halfHeight这条路径一定得不出解
for(int i=0;i<N+1;i++)
for(int j=0;j<2*halfHeight+1;j++)
res[i][j]=-1;
res[0][halfHeight]=0;//sum=10
int high;
for(int i=1;i<N+1;i++){
if(H[i]==0)
break;
high=H[i];
for(int j=0;j<2*halfHeight+1;j++)
{
if(res[i-1][j]!=-1){
res[i][j]=Math.max(res[i][j],res[i-1][j]);//第i块砖不放置
}
if(j+high<=(2*halfHeight)&&res[i-1][j+high]!=-1){
res[i][j]=Math.max(res[i][j],res[i-1][j+high]+high);//放A砖块上

}
if(j-high>=0&&res[i-1][j-high]!=-1){
res[i][j]= Math.max(res[i][j],res[i-1][j-high]);//放B砖块上
}

}
}
int max=-1;;
for(int i=1;i<=N;i++){
if(res[i][halfHeight]>max&&res[i][halfHeight]!=-1&&res[i][halfHeight]!=0)
max=res[i][halfHeight];
}
System.out.println(max);
}
}

编辑于 2017-09-28 16:40:34 回复(0)

vitabrevis

import java.util.*;

public class Main{

public static void main(String[] args){

Scanner sc=new Scanner(System.in);

int n=sc.nextInt();

int[] h=new int[n];

int sum=0;

for(int i=0;i<n;i++){

h[i]=sc.nextInt();

sum+=h[i];

}

int res=packaging(h,h,sum/2);

int half=sum-res;

System.out.print(res==half?res:-1);

}

private static int packaging(int[] W,int[] V,int target){

int len=W.length;

int[] f=new int[target+1];

for(int i=0;i<len;i++)

for(int j=target;j>=W[i];j--){

f[j]=Math.max(f[j],f[j-W[i]]+V[i]);

}

return f[target];

}

经典的01背包问题，可是为什么只通过30%，n=19，h={88242, 313, 1991, 4207, 2483 ,1763 ,224 ,16 ,582, 22943, 28632 ,47682 ,378 ,90 ,88 ,43 ,117,19 ,8}无法通过，正解输出99901，而我的程序输出-1，有没有大神解答？？？？

发表于 2017-08-17 00:26:57 回复(2)

C/C++

一纸枫叶

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n;
int height[50];
int sum[50];
int res = 0;

void dfs(int start, int sum1, int sum2);

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> height[i];
	}
    sort(height, height + n);
    for(int i = 0; i < n; ++i){
        for(int j = 0; j <= i; ++j){
            sum[i] += height[j];
        }
    }
	dfs(n - 1, 0, 0);
	if (res == 0)
		cout << -1 << endl;
	else
		cout << res << endl;
}

void dfs(int start, int sum1, int sum2) {
	if (sum1 == sum2) {
		res = max(res, sum1);
	}
	if (start == -1) {
		return;
	}
	if (sum2 > 500000) {
		return;
	}
	if (sum1 + sum[start] < sum2) {
		return;
	}
	if (sum1 + sum2 + sum[start] <= res * 2) {
		return;
	}
	dfs(start - 1, min(sum1 + height[start], sum2), max(sum1 + height[start], sum2));
	dfs(start - 1, min(sum2 + height[start], sum1), max(sum2 + height[start], sum1));
	dfs(start - 1, sum1, sum2);
}

发表于 2017-08-15 21:28:00 回复(1)

****

  //这个动态规划哪出错了么，只对30%，求大神解答 
  importjava.util.*; 
  publicclassMain{ 
      publicstaticvoidmain(String[] args) 
          { 
          Scanner sc=newScanner(System.in); 
          intn=sc.nextInt(); 
          int[]ch=newint[n]; 
          intsum=0; 
          for(inti=0;i<n;i++){ 
              ch[i]=sc.nextInt(); 
              sum+=ch[i]; 
          } 
          if(sum%2!=0){ 
              System.out.println(-1); 
          } 
          else{ 
              int[]arr=newint[sum/2+1]; 
          for(inti=0;i<n;i++){ 
              for(intj=sum/2;j>=ch[i];j--){ 
                  arr[j]=Math.max(arr[j],arr[j-ch[i]]+ch[i]); 
              } 
          } 
          if(arr[sum/2]==sum/2) 
              { 
              System.out.println(arr[sum/2]); 
          } 
          else{ 
              System.out.println(-1); 
          } 
                
                
          } 
            
            
            
      } 
  } 

发表于 2017-08-15 10:56:13 回复(0)

风苇

看了我是来搞笑的的解析，写了个java版的

import java.util.Arrays;
import java.util.Scanner;

public class pileBricks {
	static int[] arr = new int[52];
	static int[] sum = new int[52];
	static int n;
	static int ans = 0;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		for(int i = 1; i <= n; i++){
			arr[i] = sc.nextInt();
		}
		
		Arrays.sort(arr, 1, n);
		for(int i = 1; i <= n; i++)
			sum[i] = sum[i-1] + arr[i];
		
		dfs(n, 0, 0);
		if(ans == 0)
			System.out.println(-1);
		else{
			System.out.println(ans);
		}
		
	}
	public static void dfs(int n, int sum1, int sum2){
		if(sum1 == sum2)
			ans = Math.max(ans, sum1);
		if(n == 0)
			return;
		if(sum2 > 500000)
			return;
		if(sum1 + sum[n] < sum2)
			return;
		if((sum1+sum2+sum[n]) <= ans*2)
			return;
		dfs(n-1, Math.min(sum1+arr[n], sum2), Math.max(sum1+arr[n], sum2));
		dfs(n-1, Math.min(sum2+arr[n], sum1), Math.max(sum2+arr[n], sum1));
		dfs(n-1, sum1, sum2);
	}
}

发表于 2017-04-24 17:50:23 回复(1)

堆砖块

输入描述:

输出描述:

输入

输出

借鉴前面几位大神的代码，分析都写在代码中

问题信息

热门推荐

通过挑战的用户

相关试题