[洛谷2744] 量取牛奶

传送门

搜索

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
#define N 110
using namespace std;

int n,m,a[N],ans[N],v[N];
bool bj[N];

int gi() {
  int x=0,o=1; char ch=getchar();
  while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
  if(ch=='-') o=-1,ch=getchar();
  while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
  return o*x;
}

void update(int num) {
  if(num<ans[0]) {
    ans[0]=num;
    for(int i=1; i<=num; i++) ans[i]=a[i];    
  }
  if(num>ans[0]) return;
  for(int i=1; i<=num; i++) {
    if(a[i]<ans[i]) {
      ans[0]=num;
      for(int j=1; j<=num; j++)
    ans[j]=a[j];
      return;
    }
    if(a[i]>ans[i]) return;
  }
}

void dfs(int num, int sum) {
  if(num>ans[0]) return;
  if(sum>m) return;   
  for(int i=a[num-1]; i<=n; i++) {
    if(!bj[i]) {
      bj[i]=1,a[num]=i;
      if((m-sum)%v[i]==0) {
    update(num),bj[i]=0,a[num]=0;
    return;
      }
      dfs(num+1,sum+v[i]);
      bj[i]=0,a[num]=0;
    }
    else dfs(num,sum+v[i]);  
  }
}

int main() {
  m=gi(),n=gi(),ans[0]=1<<30,a[0]=1;
  for(int i=1; i<=n; i++) v[i]=gi();
  dfs(1,0);
  printf("%d ", ans[0]);
  for(int i=1; i<=ans[0]; i++) {
    ans[i]=v[ans[i]];
  }
  sort(ans+1,ans+ans[0]+1);
  for(int i=1; i<=ans[0]; i++) {
    printf("%d ", ans[i]);
  }
  return 0;
}