1 条题解
-
2
(冷知识:这一题测试点名字和B1凑在一起刚好是
remember的前缀)这种要求最优的一般先考虑
dp。于是我们可以发现这题可以转化为最多的数使得这几个数之和等于 。
还是一个比较裸的01背包问题。
#include <cstdio> #include <iostream> using namespace std; int n,m,s; int a[201],dp[200005]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i]; s+=a[i]; } int t=s-m; for(int s=1;s<=t;s++) dp[s]=-1e9; for(int i=1;i<=n;i++) { for(int sh=t;sh>=a[i];sh--) { if(dp[sh-a[i]]!=-1e9) { dp[sh]=max(dp[sh],dp[sh-a[i]]+1); } } } cout<<dp[t]; return 0; }
- 1
信息
- ID
- 10
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- 递交数
- 196
- 已通过
- 21
- 上传者