团体程序设计天梯赛-练习集 L3-001 凑零钱

DFS T一个点29分代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;
int n,m;
int money[10005];
int recorder[10005];
bool dfs(int no,int curPos,int remainValue){
    recorder[no]=money[curPos];
    if(remainValue==0)return true;
    int upp=upper_bound(money+1,money+n+1,remainValue)-money;
    for(int i=curPos+1;i<upp;i++){
        if(dfs(no+1,i,remainValue-money[i]))return true;
        else i=upper_bound(money+1,money+n+1,money[i])-money-1;
    }
    recorder[no]=0; //忘加了这个,回溯差点没做好
    return false;
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",money+i);
    sort(money+1,money+n+1);
    bool flag=dfs(0,0,m);
    if(!flag)printf("No Solution");
    else{
        int i=1;
        while(recorder[i]!=0){
            if(i!=1)printf(" ");
            printf("%d",recorder[i++]);
        }
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注