[CSP-S模拟测试]:答题（meet in the middle）

题目传送门（内部题142）

输入格式

　　输入文件的第一行为两个数$n,P$。
　　接下来一行$n$为个正整数，表示每道题的分数。

输出格式

　　输出一行一个正整数，为至少需要获得的分数。

样例

样例输入：

2 0.5
1 2

样例输出：

数据范围与提示

　　设一道题分数的最大值为$m$。
　　对于$50\%$的数据，满足$n\leqslant 20$。
　　对于另$20\%$的数据，满足$m\leqslant 1,000$。
　　对于$100\%$的数据，满足$2\leqslant n\leqslant 40,1\leqslant m\leqslant 10^6$。

题解

$n^{20}$爆搜，然后可以预处理后$20$个，然后用$meet\ in\ the\ middle$就好了。

时间复杂度：$\Theta(2^{\frac{n}{2}})$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

int n;

int a[50],L,R,sum,f[30000001],g[3000001],mx;

long long qpow;

double P;

bool judge(int x)

{

	long long res=0;

	for(int i=0;i<(1<<R);i++)if(g[i]<=x)res+=f[min(mx,x-g[i])];

	return ((double)res/qpow)<P;

}

int main()

{

	scanf("%d%lf",&n,&P);

	L=n/2;R=n-L;qpow=pow(2LL,n);

	for(int i=1;i<=n;i++)

	{

		scanf("%d",&a[i]);

		sum+=a[i];

		mx+=(i<=L)*a[i];

	}

	for(int i=0;i<(1<<L);i++)

	{

		int res=0;

		for(int j=1;j<=L;j++)if(i&(1<<(j-1)))res+=a[j];

		f[res]++;

	}

	for(int i=1;i<=sum;i++)f[i]+=f[i-1];

	for(int i=0;i<(1<<R);i++)

	{

		int res=0;

		for(int j=L+1;j<=n;j++)if(i&(1<<(j-L-1)))res+=a[j];

		g[i]=res;

	}

	int lft=0.0,rht=sum,res=sum;

	while(lft<=rht)

	{

		int mid=(lft+rht)>>1;

		if(judge(mid))lft=mid+1;

		else{rht=mid-1;res=mid;}

	}

	printf("%d",res);

	return 0;

}

rp++

巴特西