90分求救
  • 板块B3635 硬币问题
  • 楼主Gohldg
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/7/4 11:19
  • 上次更新2023/11/3 11:40:45
查看原帖
90分求救
757214
Gohldg楼主2023/7/4 11:19
#include <iostream>
using namespace std;
int a[4]={0,11,5,1};
int b[100001];
int n,ans=2147483647;
void dfs(int sum,int cnt){
    if(sum==n){
        ans=min(ans,cnt);
        return ; 
    }
	for(int i=1;i<=3;i++){
		if(sum+a[i]>n){
			continue;
		}
	    sum+=a[i];
	    dfs(sum,cnt+1);
	    sum-=a[i];
	}
}
int main(){
    cin>>n;
    if(n%11==0){
    	ans=n/11;
	}else if(n%11==1){
		ans=n/11+1; 
	}else if(n%11==2){
		ans=n/11+2; 
	}else if(n%11==3){
		ans=n/11+3; 
	}else if(n%11==4){
		ans=n/11+2;
	}else if(n%11==5){
		ans=n/11+1;  
	}else if(n%11==6){
		ans=n/11+2;
	}else if(n%11==7){
		ans=n/11+3;  
	}else if(n%11==8){
		ans=n/11+4; 
	}else if(n%11==9){
		ans=n/11+5; 
	}else if(n%11==10){
		ans=n/11+2; 
	}else if(n%5==0){
		ans=n/5;
	}else if(n%5==1){
		ans=n/5-1;
	}else if(n%5==2){
		ans=n/5;
	}else if(n%5==3){
		ans=n/5+1;
	}else if(n%5==4){
		ans=n/5+4;
	}else dfs(0,0);
    cout <<ans;
    return 0;
}
2023/7/4 11:19
加载中...