[NC19158] 失衡天平

1
2
3
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

终于Alice走出了大魔王的陷阱，可是现在傻傻的她忘了带武器了，这可如何是好???这个时候，一个神秘老人走到她面前答应无偿给她武器，但老人有个条件，需要将所选武器分别放在天平的两端，若天平平衡则可以将天平上的所有武器拿走，还好这个天平锈迹斑斑，只要两端重量相差小于等于m就会保持平衡，Alice傻傻的认为越重的武器越好，求Alice最多能拿走的武器总重量。（不限操作次数）

输入描述:

第一行2个整数 n, m;
第二行n个整数x，分别表示n件武器的重量。
1 <= n <= 100; 0 <= m <= 100; 1 <= x <= 100;

输出描述:

一个整数，表示Alice最多能拿走的武器总重量。

示例1

输入

1
2
5 4
1 5 61 65 100

输出

1
132

说明

1
可以称两次，第1次：(1 ; 5),第二次(61 ; 65)。

示例2

输入

1
2
5 0
10 20 30 40 100

输出

1
200

说明

1
称一次，(10,20,30,40 ; 100)。

题解

题目解析

一道类似于背包的dp题.解题关键在于如何处理放置的物品.事实上,我们需要开一个二位数组作为dp数组.再就是找到这个问题的状态转移方程.

我们把背包的思想带入其中,使用了两个dp变量:

  • 已经到了第i个物品
  • 前i个物品组合放置之后的两边之差

那么我们可以得到一个递推的想法:

1
2
3
4
5
6
7
dp[i][j]//也就是到了第i个物品经过放置或者不放置组成了天平两边相处为j的最大值.
dp[i][j] = max(dp[i-1][j],max(dp[i-1][j-a[i]]+a[i],dp[i-1][j+a[i]]+a[i]);
//关于dp[i][j]的组成有三种情况:
//1.到i-1个物品已经组成j为差的了,到第i个物品我不往上放.
//Remark:到i-1个物品组成j-a[i]和j+a[i]都可以经过左右侧不同的放置最后在第i个物品达到j为差的情况.
//2&3.到i-1个物品已经组成abs(j-a[i])(因为有可能是负的,因为左右可以调整嘛,所以加绝对值的意义就像第i-1个物品的时候左右互换了)/j+a[i]为差的了,到第i个物品我看着选择在左或右放上东西最后使得j为差.
//Remark:这里的到第i个物品指的是到第i种物品所组成的所有可能,其可能包含i放的情况,也可能包含i没往上放的情况.

那么我们顺理就可以得到它的状态转移方程了:

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
const int MAXN = 110;
using namespace std;

int a[MAXN],dp[MAXN][MAXN*MAXN*2];

int main(){
	int n,m;
	cin >> n >> m;
	for(int i=1;i<=n;i++) cin >> a[i];
	memset(dp,-0x3f3f3f3f,sizeof(dp));
	dp[0][0] = 0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=MAXN*MAXN*2;j++){
			dp[i][j] = max(dp[i-1][j],max(dp[i-1][abs(j-a[i])]+a[i],dp[i-1][j+a[i]]+a[i]));
		}
	}
	int ans = 0;
	for(int i=0;i<=m;i++){
		ans = max(dp[n][i],ans);
	}
	cout << ans;
	return 0;
}