题解 CF339C 【Xenia and Weights】
aRenBigFather
2018-12-15 15:57:50
一个贪心方法，不能过完但是可以得很多分(开始就是这样写的)
```cpp
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
string aa;
bool flag[20];
ll lweight,rweight;
int m;
vector<int> ans;
int last = -1;
int getmin(int low){
for(int i=low+1;i<=10;i++)
if(flag[i] && i != last) {
last = i;
return i;
}
return -1;
}
int main(){
cin >> aa >> m;
memset(flag,0,sizeof flag);
for(int i=0;i<aa.size();i++)
if(aa[i] == '1') flag[i+1] = true;
lweight = 0,rweight = 0;
bool cant = false;
for(int i=1;i<=m;i++){
if(i & 1){
//put to left
int dt = rweight - lweight;
int mincan = getmin(dt);
if(mincan == -1){
cant = true;
break;
}
lweight += mincan;
ans.push_back(mincan);
}else{
//put to right
int dt = lweight - rweight;
int mincan = getmin(dt);
if(mincan == -1){
cant = true;
break;
}
rweight += mincan;
ans.push_back(mincan);
}
}
if(cant){
cout << "NO" << endl;
return 0;
}else{
cout << "YES" << endl;
for(int i=0;i<ans.size();i++){
if(i == 0) cout << ans[i];
else cout << " " << ans[i];
}
}
return 0;
}
```
正解是很简单的dfs
纪录路径的时候有个方法直接开全局变量(以前都不知道可以这样，然后就不用dfs传路径参数下去了)
```cpp
#include <bits/stdc++.h>
using namespace std;
string aa;
bool flag[20];
int ans[1010];
int m;
bool can = false;
bool dfs(int step,char nowdir,int lastWei,int lwei,int rwei){
//cout << "step:" << step << " lwei:" << lwei << " rwei:" << rwei << endl;
if(step == m+1){
return true;
}
if(nowdir == 'R'){
//放右边
int dt = lwei - rwei;
bool cant = true;
for(int i=dt+1;i<=10;i++){
if(flag[i] && i != lastWei){
cant = false;
ans[step] = i;
if(dfs(step+1,'L',i,lwei,rwei+i)) return true;
}
}
if(cant) return false;
}else if(nowdir == 'L'){
//放左边
int dt = rwei - lwei;
bool cant = true;
for(int i=dt+1;i<=10;i++){
if(flag[i] && i != lastWei){
cant = false;
ans[step] = i;
if(dfs(step+1,'R',i,lwei+i,rwei)) return true;
}
}
if(cant) return false;
}
}
int main(){
cin >> aa >> m;
memset(flag,0,sizeof flag);
for(int i=0;i<aa.size();i++)
if(aa[i] == '1') flag[i+1] = true;
if(dfs(1,'L',-1,0,0)){
cout << "YES" << endl;
for(int i=1;i<=m;i++){
if(i == 1) cout << ans[i];
else cout << " " << ans[i];
}
}else{
cout << "NO" << endl;
}
return 0;
}
```