2022-04-13 21:15 北京交通大学 后端
关注
#华为机试#
华为4.13第三题分糖果有大佬过吗？我用01背包只过了5%。。。
华为4.13第三题分糖果有大佬过吗？我用01背包只过了5%。。。
全部评论
Comrades
华中科技大学 游戏后端
把转移方程写一下吧，你这个思路好像都有问题。
LBJHan 楼主
楼主 北京交通大学 后端
附上代码，求大佬指教！！！
#include <bits/stdc++.h>
// we have defined the necessary header files here for this problem.
// If additional header files are needed in your program, please import here.
using namespace std;
int a[105];
int dp[10005];
int path[105][10005];
bool vis[105];
int main()
{
// please define the C++14 input here. For example: int a,b; cin>>a>>b;;
// please finish the function body here.
// please define the C++14 output here. For example:cout<<____<<endl;
int n;
cin >> n;
int sum = 0;
for(int i=0; i<n; i++){
cin >> a[i];
sum += a[i];
vis[i] = false;
}
if(n==1 || (sum&1)){
cout << -1 << endl;
}else{
sum = sum >> 1;
//cout << "sum = " << sum << endl;
memset(dp, 0, sizeof(dp));
memset(path, 0, sizeof(path));
for(int i=0; i<n; i++){
for(int j=sum; j>=a[i]; j--){
if(dp[j] <= dp[j-a[i]] + a[i]){
dp[j] = dp[j-a[i]] + a[i];
path[i][j] = 1;
}
}
}
if(dp[sum] != sum){
cout << -1 << endl;
}else{
cout << dp[sum] << endl;
vector<int> vec;
int i=n-1, j=sum;
while(i>=0 && j>=0){
if(path[i][j]){
j=j-a[i];
vec.push_back(a[i]);
vis[i] = 1;
}
i--;
}
for(int i=vec.size()-1; i>=0; i--){
cout << vec[i] << (i == 0 ? '\n' : ' ');
}
vec.clear();
for(int i=0; i<n; i++){
if(vis[i]) continue;
vec.push_back(a[i]);
}
//sort(vec.begin(), vec.end());
for(int i=vec.size()-1; i>=0; i--){
cout << vec[i] << (i == 0 ? '\n' : ' ');
}
}
}
return 0;
}
相关推荐
