L3-001. 凑零钱

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目链接：https://www.patest.cn/contests/gplt/L3-001

动态规划

这道题一看就知道应该用背包思想来做，不过想了好久没什么思路(dp实在是渣)，最后还是鼓捣出来了ac代码QAQ，细节加了注释。

代码如下：

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<stack>

 using namespace std;

 const int INF=-0x3fffffff;

 stack<int>s;

 int dp[],pre[],a[];

 int main(void){

     //freopen("in.txt","r",stdin);

     for(int i=;i<=;++i){

         dp[i]=INF;

         pre[i]=-;

     }

     dp[]=;

     int n,m;

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;++i)

         scanf("%d",&a[i]);

     sort(&a[],&a[]+n);

     for(int i=;i<=n;++i){

         for(int j=m;j>=a[i];--j){

             if(dp[j]<=dp[j-a[i]]+){
                /*加等号是因为在硬币个数相同的情况下，若其中一枚更大，相对另一枚更小，从而使得字典序最小*/

                 dp[j]=dp[j-a[i]]+;

                 pre[j]=j-a[i];/*记录路径*/

             }

         }

     }

     if(dp[m]>){

         int k=m;

         while(pre[k]){

             s.push(k-pre[k]);

             k=pre[k];

         }

         printf("%d",k);

         while(!s.empty()){

             printf(" %d",s.top());

             s.pop();

         }

         printf("\n");

     }else printf("No Solution\n");

     return ;

 }