#36939: C++解答(我用dfs)


tommyyang1025@gmail.com (Tommy Yang)

學校 : 不指定學校
編號 : 168835
來源 : [60.248.154.141]
最後登入時間 :
2024-05-20 09:31:07
b511. 換銅板 -- 清華 MOOCs 2014 程式設計導論期末考 | From: [180.176.188.112] | 發表日期 : 2023-08-17 19:48

#include <bits/stdc++.h>
using namespace std;
int n,sum,p;
vector<int> v,a;
bool b = false;

int ad(vector<int> &a){
    int ans = 0;
    for(int i = 0 ; i<a.size() ; i++){
        ans+=v[i]*a[i];
    }
    return ans;
}
void dfs(){
    int da = ad(a);
    if(da>=sum){
        if(da==sum){
            string ans = "(" + to_string(a[0]);
            for(int i = 1 ; i<n ; i++){
                ans+=",";
                if(i<a.size()){
                    ans+=to_string(a[i]);
                }
                else{
                    ans+="0";
                }
            }
            ans+=")";
            cout << ans << endl;
        }
        b = true; return;
    }
    else if(a.size()==n){
        return;
    }
    else{
        for(int i = 0 ; i<=p ; i++){
            a.push_back(i);
            dfs();
            if(b){
                a.pop_back();
                b = false;
                return;
            }
            a.pop_back();
        }
    }
}
int main(){
    
    cin>>n;
    int mi = 100001;
    for(int i = 0 ; i<n ; i++){
        int temp;
        cin>>temp;
        v.push_back(temp);
        mi = min(mi,temp);
    }
    cin>>sum;
    p = sum/mi;
    if(sum%mi!=0){
        p++;
    }
    dfs();

    return 0;
}

 
ZeroJudge Forum