记录编号	302105	评测结果	AAAAAAAAAA
题目名称	硬币问题	最终得分	100
用户昵称	GROWL GOOD BOYส็	是否通过	通过
代码语言	C++	运行时间	0.341 s
提交时间	2016-09-03 11:09:15	内存使用	0.86 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<iostream>
#include<vector>

using namespace std;

const int maxv=100010;

int N,M;

int fma[maxv],fmi[maxv],data[110];


int dp(int x)
{
    if(fma[x]!=-1)return fma[x];
    if(x==0) return fma[x]=0;
    int& ha=fma[x];
    ha=-0x7ffff;
    for(int i=1;i<=N;i++)
    {
        if(x-data[i]>=0)ha=max(ha,dp(x-data[i])+1);   
    }
    return ha;
};

int dpi(int x)
{
    if(fmi[x]!=-1)return fmi[x];
    if(x==0) return fmi[x]=0;
    int& ha=fmi[x];
    ha=0x7ffffff;
    for(int i=1;i<=N;i++)
    {
        if(x-data[i]>=0)ha=min(ha,dpi(x-data[i])+1);   
    }
    return ha;
};

void print_1(int V)
{
     for(int i=1;i<=N;i++)
     {
      if(V-data[i]>=0&&fma[V-data[i]]==fma[V]-1)
      {
         printf("%d ",i);
         print_1(V-data[i]);
         break;                                      
      }
     }
}
void print_2(int V)
{
     for(int i=1;i<=N;i++)
     {
      if(V-data[i]>=0&&fmi[V-data[i]]==fmi[V]-1)
      {
        printf("%d ",i);
         print_2(V-data[i]);   
         break;                                    
      }
     }
}
int main()
{
    freopen("kouka.in","r",stdin);
    freopen("kouka.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)scanf("%d",&data[i]);
    memset(fma,-1,sizeof(fma));
    memset(fmi,-1,sizeof(fmi));
    int Ans1=dpi(M),Ans2=dp(M);
    if(Ans1>99999999)Ans1=-1;
    if(Ans2==0)Ans2=-1;
    printf("%d %d",Ans1,Ans2);
    printf("\n");
    if(Ans2!=-1)
    print_2(M); 
    printf("\n");
    if(Ans1!=-1)
    print_1(M);    
    fclose(stdin);
    fclose(stdout);
    return 0;
}