上海计算机学会2024年10月月赛C++乙组T2子集和
发布时间
阅读量：
阅读量
子集和
内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定n个数字a₁,a₂,…,aₙ，请确定是否存在一组子集使得这些子集内所有元素的总和正好等于给定整数t？
输入格式
- 第一行：单个整数 n
- 第二行：n 个整数 a1,a2,…,an
输出格式
- 如果可以达到目标，输出
Yes，否则输出No
数据范围
- 针对大约3成的数据情况（即占总数据量的3/1至2/9），约束条件为 n 值在2至2O的数量级范围内。
- 针对约半数的数据量级（即占总测试用例的约5至9.999%，对应n值在5至5O之间）。
- 整体而言的所有情况均满足约束条件：n值介于1至O(n)的数量级范围内。
- 额外补充的情况（这些情况不会影响最终评分结果），其参数范围扩展至更大的规模：n值可达O(n)级别。
样例数据
输入:
4 10
1 2 3 9
输出:
Yes
输入:
4 12
1 2 3 5
输出:
No
解析：01背包 ，详见代码：
#include <bits/stdc++.h>
using namespace std;
int n, t;
int a[305];
bool dp[300005];//dp[i]表示是否能凑成和为i
int main() {
cin >> n >> t;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
dp[0] = 1;
for(int i = 1; i <= n; i++) {//01背包外循环，循环每个数
//01背包内循环，倒序判断数字j能否凑出来
for(int j = t; j >= a[i]; j--) {
dp[j] = dp[j] || dp[j - a[i]];
}
if (dp[t]) {//如果能凑出t
cout << "Yes";//输出yes，返回
return 0;
}
}
cout << "No";
return 0;
}全部评论 (0)
还没有任何评论哟~