题解 CF339C 【Xenia and Weights】

aRenBigFather · 2018-12-15 15:57:50 · 题解

一个贪心方法，不能过完但是可以得很多分(开始就是这样写的)

#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传路径参数下去了)

#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;
}