蓝桥 7.11 dp
最编程
2024-07-11 21:03:53
...
2.砝码称重 - 蓝桥云课 (lanqiao.cn)
思路
动态规划的核心思想是将问题分解成更小的子问题,并存储子问题的解,以避免重复计算
数组 dp[i][j]
表示使用前 i
个砝码可以称出的重量为 j
的数量
更新过程如下:
1.初始化:dp[0][0] = 0;
2.对于每一个砝码wi:
ac代码
#include<bits/stdc++.h>
typedef long long ll;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const ll M=2e5+10;
const int N=110;
int dp[N][M]={0};
using namespace std;
int main()
{
IOS;
int n,num=0;
cin>>n;
int w[N];
ll ans=0;
for(int i=1;i<=n;i++)
{
cin>>w[i];
num+=w[i];
}
dp[0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=num;j++)
{
dp[i][j] = dp[i-1][j] + dp[i-1][abs(j-w[i])] + dp[i-1][j+w[i]];
//cout<<dp[i][j]<<" ";
}
//cout<<endl;
}
for(int i=1;i<=num;i++)
{
if(dp[n][i]) ans++;
}
cout<<ans;
return 0;
}
推荐阅读
-
P8635 ["蓝桥杯 "2016 年 AB 省]四则运算之和
-
牛客小白月赛102(A,B,C,D,E)(思维,分层图,换根dp)-E题
-
Acwing 状态压缩 DP
-
CSP-J/S 重匹配算法 线性 DP-DP 算法 三元素
-
蓝桥杯-财务管理
-
岩谷 P11045 [蓝桥杯 2024 省 Java B] 最佳分组
-
Codeforces 第 976 轮(第 2 单元)(A、B、C、D、E)并发检查集、区间合并、概率 dp-C 问题
-
[LeetCode]每日一题 2024_10_1 最低票价(记忆搜索/DP)
-
蓝桥杯[物联网]零基础到国家奖之路:XVI.矩阵密钥的扩展模块--第三节 MDK 代码
-
蓝桥杯 - STM32G431RBT6(TIM 定时器的输出频率和占空比,以及详细原理和用法)