排位赛#1题解
2024-11-15 22:57:14
发布于：广东
18阅读
0回复
0点赞
T1
0123456背包板子题
表示能否拼成长度为 的钢条，如果 可以拼而且恰好有一根长度为 的木条就可以拼
#include <iostream>
#include <cstdio>
#include <vector>
#define int long long
using namespace std;
vector <int> a;
bool dp[500005];
signed main(){
cin.tie(nullptr) -> sync_with_stdio(0);
cout.tie(nullptr) -> sync_with_stdio(0);
int n, x, z, m;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> x >> z;
for(int j = 1; j <= z; z -= j, j <<= 1) a.push_back(x * j);//二进制优化 这么搞不仅能满足所有的组合还能减小时间复杂度
if(z) a.push_back(x * z);
}
dp[0] = 1;
for(int i:a){
for(int j = 500000; j >= i; j--) dp[j] |= dp[j - i];//相当于01背包
}
cin >> m;
while(m--){
cin >> x;
cout << (dp[x] ? "Yes\n" : "No\n");
}
return 0;
}
（未完成）
这里空空如也
有帮助，赞一个