acm1746.cpp

设有n种不同面值a1, a2,…, an的邮票

#include <iostream>
using namespace std;

int main(){
	int text;
	cin>>text;
	while(text--){
		int max=0,num,v,i,j,n,m,a[11],k[11]={0};
		int r,s,s1;
		int flag[1000]={0};//用数组flag[i]存储是否能产生面值为i邮票组合。
		cin>>n>>m;
		for(i=1;i<=n;i++){
			cin>>a[i];
			if(a[i]>max)
				max=a[i];//max为最大的面值。
		}
		i=1; k[i]=-1;
		while(i>=1){  
			while(k[i]<m){
				k[i]=k[i]+1;
				num=0; v=0;
				for(j=1;j<=i;j++){
					num=num+k[j]; 
					v=v+k[j]*a[j];
				}
				if(num<=m){
					flag[v]=1;
					if(i<n){
						i=i+1;
						k[i]=-1;
					}
				}
			}//回溯
			i=i-1;
		}
		//for(i=1;i<=m*max;i++)//输出数组flag串。
		//	cout<<flag[i];		
		//cout<<endl;
		s=0; s1=0; //s最长的连续1串的长度。s1为当前的连续1串的长度。
        r=0;//记录最长1串的最后一个'1'在数组flag中的位置。
		flag[m*max+1]=0;//为以下查找方便增加数组长度。
		for(i=1;i<=m*max+1;i++)
		{
			if(flag[i]==0)
			{
				if(s1>s){ s=s1; r=i-1;}//更新最长连续1串的长度，记录最长1串的
				s1=0;                  //最后一个'1'在数组flag中的位置。
			}
			else
				s1++;
		}
		cout<<r-s+1<<' '<<r<<endl;
	}
	return 0;
}