TLE过数学节

题目描述:

今天是察哈尔省的数学节，TLE打算过来与民同乐。其中有一道题：已知 n 个整数x1,x2,…,xn 以及一个整数k（k<n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为：

3＋7＋12=22　　3＋7＋19＝29　　7＋12＋19＝38　　3＋12＋19＝34。

现在，要求你计算出和为素数共有多少种。例如上例，只有一种的和为素数：3＋7＋19＝29。

输入格式:

第一行共有2个自然数 n，k。
第二行是一个长度为n的序列 x1,x2,…,xn 。

输出格式:

输出共一行，为总方案数。由于该数可能很大，请输出在mod 1000000007下的值。

样例输入:

4 3
3 7 12 19

样例输出:

1

提示:

对于50%的数据:

n≤10，k≤5。

对于100%的数据:

1≤n≤100，0≤xi≤300，1≤k≤n。

时间限制: 1000ms
空间限制: 128MB

代码模板:

#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
int a[101], b[30001], c[30001], f[101][30001], n,m, maxn,len=0;

int main(){
	ios :: sync_with_stdio( false );  //读入优化
	cin >> n >> m;
	for (int i=1; i<=n; i++) cin>>a[i], maxn+=a[i];
	
	for ( int i=2; i<= maxn ; i++){     //埃式筛法,先预处理出所有的质数
		if ( b[i] == 0 ){
			c[ ++len ] = i;
			for (int j=2; j*i <= maxn ; j++)
				b[ j*i ]=1;			
		}			
	}	
	f[0][0]=1;
	//Dp  O(100 * 100 *30000)
	for (int i=1; i<=n; i++){
		for (int k=min(i,m); k>=1; k--){//三维数组开不出来，开两维数组需要从后往前更新
			for (int j=a[i]; j <= maxn; j++){  //这一维可以不用从后更新
				f[k][j] = (        ) % MOD;
			}
		}
	}
	long long ans=0;
	for (int j=1; j <= len; j++){
		ans +=       ;
	}		
	cout  <<  ans % MOD;
	return 0;
}

本题是一个01背包问题。

n个数看作n件物品，背包的容量为300*n，f[i,k,j]表示，前i个物品，当前取k个过来，j容量能取到的方案数。

f[i] [k] [j]  =   (  f[i-1] [k] [j] +f[i-1][k-1] [ j-a[i] ] ) % 1000000007   ( j- a[i] > 0 )

背包时间效率是：O(300*n2)，实现时只要二维就可以，不需要开三维的空间。

最后把300*n范围内的质数筛出，累加即为答案。

大家可以看模版理解一下，自己填空。

复 完整代码 :

#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
int a[101], b[30001],c[30001], f[101][30001], n,m, maxn,len=0;

int main(){
	ios :: sync_with_stdio( false );  //读入优化
	cin >> n >> m;
	for (int i=1; i<=n; i++) cin>>a[i], maxn+=a[i];
	
	for ( int i=2; i<= maxn ; i++){     //埃式筛法,先预处理出所有的质数
		if ( b[i] == 0 ){
			c[ ++len ] = i;
			for (int j=2; j*i <= maxn ; j++)
				b[ j*i ]=1;			
		}			
	}	

	f[0][0]=1;
	//Dp  O(100 * 100 *30000)
	for (int i=1; i<=n; i++){
		for (int k=min(i,m); k>=1; k--){//三维数组开不出来，开两维数组需要从后往前更新
			for (int j=a[i]; j <= maxn; j++){  //这一维可以不用从后更新
				f[k][j] = ( f[k][j]+f[k-1][j-a[i]] ) % MOD;
			}
		}
	}
	long long ans=0;
	for (int j=1; j <= len; j++){
		ans += f[m][c[j]];
	}		
	cout  <<  ans % MOD;
	return 0;
}