记录编号	84349	评测结果	AAAAAAAAAAAAA
题目名称	[USACO Nov13] 不设找零	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.213 s
提交时间	2013-12-12 18:43:43	内存使用	1.01 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<iomanip>
using namespace std;
const int SIZEN=100001,SIZEC=21;
int pow2[SIZEC]={1};
int sumprice[SIZEN]={0};
int value[SIZEC]={0};
int N,K;
int f[65537]={0};
bool sure[65537]={0};
int ans=-1;
queue<int> Q;
int find(int x,int money,int left,int right){//从x+1开始,钱数为money,最多买到多少
	if(left==right) return left;
	int mid=(left+right)>>1;
	if(sumprice[mid+1]-sumprice[x]>money) return find(x,money,left,mid);
	else return find(x,money,mid+1,right);
}
int getdig(int x,int t){//x的左起第t位
	return (x&pow2[K-t])>>(K-t);
}
int changedig(int x,int t,int r){
	if(r==1) return x|pow2[K-t];
	else return x&(~pow2[K-t]);
}
void printdig(int x){
	for(int i=1;i<=K;i++) cout<<getdig(x,i);
}
void DP(void){
	Q.push(0);
	f[0]=0;
	int x,u,i,temp;
	while(!Q.empty()){
		x=Q.front();Q.pop();
		if(sure[x]==true) continue;
		sure[x]=true;
		if(f[x]==N){
			temp=0;
			for(i=1;i<=K;i++) if(!getdig(x,i)) temp+=value[i];
			ans=max(ans,temp);
		}
		else{
			for(i=1;i<=K;i++){
				if(getdig(x,i)==0){
					u=changedig(x,i,1);
					temp=find(f[x],value[i],f[x]+1,N);
					if(temp>f[u]){
						f[u]=temp;
						Q.push(u);
					}
				}
			}
		}
	}
}
void init(void){
	int i;
	for(i=1;i<=20;i++) pow2[i]=2*pow2[i-1];
	scanf("%d%d",&K,&N);
	for(i=1;i<=K;i++) scanf("%d",&value[i]);
	for(i=1;i<=N;i++) scanf("%d",&sumprice[i]),sumprice[i]+=sumprice[i-1];
}
int main(){
	freopen("nochange.in","r",stdin);
	freopen("nochange.out","w",stdout);
	init();
	DP();
	printf("%d\n",ans);
	return 0;
}