1.长度之和 (length.cpp)

【问题描述】

小白有 n 种木棍，长度分别为 a1,a2,a3……an，每

种木棍都无限供应。现在小白得 到一个非负整数

L，请你帮他计算选取多少根木棍使得长度之和恰好

为L？

要求输出选取木棍数的最小值和最大值。并不需要输

出具体方案。如果不能恰好得到 长度之和为 l，则

输出"No"。

【输入格式】 length.in

第 1 行输入 n L

第 2 行输入 n 种木棍不同的长度。 【输出格式】

输出文件名为 length.out。

共一行，最小值，最大值，中间空一格。 【输入样例 1】

3 6

1 2 3

【输出样例 1】 2 6

【样例说明】

最小组合为：3+3，最大组合为：1+1+1+1+1+1. 【输入样例 2】

3 7

2 6 4

【输出样例 2】 No

【输入样例 3】 2 9

5 3

【输出样例 3】 3 3

【数据说明】

对于 40%的数据，1<=n<=10，1<=l<=100,1<=ai<=l。

对于 100%的数据，1<=n<=1000，

1<=l<=20000,1<=ai<=l。

#include<bits/stdc++.h>
using namespace std;
int mi[1010][20010],mx[1010][20010],f[1010],a[1010],n,l,minn=INT_MAX,maxx=INT_MIN;
int main(){
    cin>>n>>l; 
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    f[0]=true;
    for(int i=1;i<=n;i++){
        for(int j=a[i];j<=l;j++){
        	if(f[j-a[i]]){
        		mi[i][j]=min(mi[i-1][j],mi[i-1][j-a[i]]+1);
        		mx[i][j]=max(mx[i-1][j],mx[i-1][j-a[i]]+1);
        		f[j]=true;
			}	
        }
    } 
    if(mi[l]!=0){
    	cout<<mi[n][l]<<" "<<mx[n][l];
	}
	else{
		cout<<"NO";
	}
    return 0;
}