游客 注册 | 登录
中文 | En

3648 - 硬币支付

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

伊娃喜欢从宇宙的各个角落收集硬币，其中包括一些其它的行星像火星。有一天，她参观了环球购物中心可以接

受各种硬币支付。然而，有了付款的特殊要求：每个账单，她必须支付的确切数额。因为她有多达104个硬币

她，她肯定需要你的帮助。你应该告诉她，对于任何给定的数量的钱，她是否可以找到一些硬币付钱。

题目输入

每个输入文件包含一个测试用例。对于每一种情况下，第一行包含2个正数：n（＜＝104，硬币的总数）和

M（＜＝102，钱伊娃金额支付）。第二行包含n个硬币的面值，都是正数。在一行中的所有数字用一个空格隔

开。

题目输出

对于每个测试案例，在一行打印面值V1 < V2 <= =…＜＝VK，V1 + V2 +…+ VK = M的所有数字必须用一个空格隔开，而且最后

一排没有多余的空间。如果这样的解不唯一，输出最小的序列。如果没有解决方案，输出“无解”代替。

注：序列{ A[1]，A[2]，……}被称为比序列{ B [ 1 ]，B [ 2 ]，……}小如果存在K＞＝1，A[i]=B [i],对于所有i< K，a[ k ] < B [K 

]。

输入/输出样例

输入格式

8 9
5 9 8 7 2 3 4 1
4 8
7 2 4 3

输出格式

1 3 5
No Solution

C++解答

#include<stdio.h>  
#include<stdlib.h>  
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int cmp(int a,int b){ 
    return a > b;  
}  
int dp[10001][101],pre[10001][101];  
int arr[10001],ans[10001];  
int main(){  
    int i,j,n,m;  
    while(scanf("%d %d",&n,&m)!=EOF){
    for(i=1;i<=n;i++){  
        scanf("%d",&arr[i]);  
    }  
    sort(arr + 1, arr + n + 1,cmp);  
    for(i=0;i<=n;i++){  
        for(j=0;j<=m;j++){  
            dp[i][j]=0;  
            pre[i][j]=0;  
        }  
    }  
    for(i=0;i<=n;i++){  
        dp[i][0]=1;  
    }  
    for(i=1;i<=n;i++){  
        for(j=arr[i];j<=m;j++){  
            if(dp[i-1][j-arr[i]]){  
                dp[i][j]=1;  
                pre[i][j]=1;  
            }  
            else{  
                dp[i][j]=dp[i-1][j];  
            }  
        }  
    }  
    if(!dp[n][m]){  
        printf("No Solution\n");  
    }  
    else{  
        int cnt=0;  
        while(n>0){  
            if(pre[n][m]){  
                ans[cnt]=arr[n];  
                m=m-arr[n];  
                n=n-1;  
                cnt++;  
            }  
            else{  
                n--;  
            }  
        }  
        for(i=0;i<cnt-1;i++){  
            printf("%d ",ans[i]);  
        }  
        printf("%d\n",ans[cnt-1]);  
    }  
	}
    return 0;  
}
请先登陆