砝码称重DP第十二届蓝桥杯省赛第一场C++A/B/研究生组
题目描述
你有一架天平和 N 个砝码,这 N 个砝码重量依次是 W1,W2,⋅⋅⋅,WN。
请你计算一共可以称出多少种不同的正整数重量?
注意砝码可以放在天平两边。
输入格式
输入的第一行包含一个整数 N。
第二行包含 N 个整数:W1,W2,W3,⋅⋅⋅,WN。
输出格式
输出一个整数代表答案。
数据范围
对于 50% 的评测用例, 1 ≤ N ≤ 15 1≤N≤15 1≤N≤15。
对于所有评测用例, 1 ≤ N ≤ 100 1≤N≤100 1≤N≤100,N 个砝码总重不超过 105。
输入样例:
3
1 4 6
输出样例:
10
样例解释
能称出的 10 种重量是:1、2、3、4、5、6、7、9、10、11。
1 = 1;
2 = 6 − 4 (天平一边放 6,另一边放 4);
3 = 4 − 1;
4 = 4;
5 = 6 − 1;
6 = 6;
7 = 1 6;
9 = 4 6 − 1;
10 = 4 6;
11 = 1 4 6。
思路
d p [ i ] [ j ] dp[i][j] dp[i][j]代表使用前i个砝码的情况下能否凑出重量为j的物品。0代表凑不出,1代表可凑出。
得到 d p dp dp数组后只需要遍历一遍 d p [ n ] [ 1 ] dp[n][1] dp[n][1]到 d p [ n ] [ s u m ] dp[n][sum] dp[n][sum]有多少种情况能凑出即可。(sum为所有砝码的总重,因为可凑出重量不可能超过总重)
状态转移方程推导
情况1——不使用第i个砝码
直接可得 d p [ i ] [ j ] = d p [ i − 1 ] [ j ] dp[i][j] = dp[i - 1][j] dp[i][j]=dp[i−1][j]
情况2——将第i个砝码放在右边
d p [ i ] [ j ] = m a x ( d p [ i ] [ j ] , d p [ i − 1 ] [ j − w [ i ] ] ) dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]]) dp[i][j]=max(dp[i][j],dp[i−1][j−w[i]]),注意放在右边是 j − w [ i ] j-w[i] j−w[i]。假定天平左端需要称的物品重量为 j j j,那么已知第 i i i个砝码是一定要放在右边的,所以剩余砝码需要凑出的重量就是 j − w [ i ] j-w[i] j−w[i]。同理可推得砝码放在左边的方程。
情况3——将第i个砝码放在左边
d p [ i ] [ j ] = m a x ( d p [ i ] [ j ] , d p [ i − 1 ] [ j w [ i ] ] ) dp[i][j] = max(dp[i][j], dp[i - 1][j w[i]]) dp[i][j]=max(dp[i][j],dp[i−1][j w[i]])
其实第i个砝码放在哪里对应的是加还是减没搞清楚也不会错反正就一加一减
解法一 y总解法
因为该解法在砝码放在左边时第二维下标可能是负数,所以第二维整体加一个偏移量让下标合法。(y总思路真是太清晰力
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
typedef long long ll;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define endl '\n'
using namespace std;
const int N = 2e5 10;
const int M = (N / 2);
int w[N];
int dp[105][N];
int main()
{
IOS;
int n;
cin >> n;
int sum = 0;
for (int i = 1; i <= n; i )
{
cin >> w[i];
sum = w[i];
}
dp[0][M] = 1;//加了一个M偏移量
int ans = 0;
for (int i = 1; i <= n; i )
{
for (int j = -sum; j <= sum; j ) //-sum代表砝码全放在左边,sum代表砝码全放在右边
{
//只要有一种方案可以凑出来,那么dp[i][j M]就是1
dp[i][j M] = dp[i - 1][j M];
if (j - w[i] >= -sum) //特判不存在的情况
dp[i][j M] = max(dp[i][j M], dp[i - 1][j - w[i] M]);
if (j w[i] <= sum) //特判不存在的情况
dp[i][j M] = max(dp[i][j M], dp[i - 1][j w[i] M]);
}
}
for (int i = 1; i <= sum; i )
if (dp[n][i M]) //如果这种凑法存在,ans
ans ;
cout << ans << endl;
return 0;
}
解法二(不需要偏移量)
总体思路差不多,但是二维的循环有了优化。
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
typedef long long ll;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define endl '\n'
using namespace std;
const int N = 2e5 10;
const int M = (N / 2);
int w[N];
int dp[105][N];
int main()
{
IOS;
int n;
cin >> n;
int sum = 0;
for (int i = 1; i <= n; i )
{
cin >> w[i];
sum = w[i];
}
dp[0][0] = 1;
for (int i = 1; i <= n; i )
{
for (int j = sum; j >= 0; j--) //不能改成从0到sum,会错
{
//这里没加特判是因为即使数组越界了值依旧是0,不会对结果造成影响,所以我就懒得写了
dp[i][j] = max(dp[i - 1][j w[i]], dp[i - 1][abs(j - w[i])]);
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
}
}
int ans = 0;
for (int i = 1; i <= sum; i )
{
if (dp[n][i])
ans ;
}
cout << ans << endl;
return 0;
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhggbfci
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13