70pts 预处理了每个硬币能到达的最远距离
查看原帖
70pts 预处理了每个硬币能到达的最远距离
121813
老子是北瓜楼主2021/7/13 11:39

真的找不出哪里还有问题了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 100003
using namespace std;

int k,n,maxn,maxval;

int a[20],r[N];
int t[20][N];
int f[N];
void getans(int num){
	int tot=0;
	for(int i=0; i<k; ++i)
	{
		if(!(num & (1<<i)))
			tot+=a[i+1];
	}
	if(maxn<tot)
		maxn=tot;
}

int main(){
	maxn=-1;
	scanf("%d%d",&k,&n);
	for(int i=1; i<=k; ++i)
		scanf("%d",&a[i]);
	for(int i=1; i<=n; ++i)
		scanf("%d",&r[i]);
	for(int i=1; i<=k; ++i)
	{
		int p=0;
		int sum=0;
		for(int j=0; j<=n; ++j)
		{
			if(sum!=0)
				sum-=r[j];
			while(sum+r[p+1]<=a[i] && p!=n) sum+=r[++p];
			t[i][j]=p;
		}
	}
	
	
	for(int i=0; i<(1<<k); ++i)
	{
		for(int j=0; j<k; ++j)
		{
			int tmp=(1<<j);
			if(i&tmp) continue;
			f[i^tmp]=t[j+1][f[i]];
			if(f[i^tmp]==n)
				getans(i^tmp);
		}
	}
	
	printf("%d",maxn);
	return 0;
}
2021/7/13 11:39
加载中...