社区讨论

RE 求助

P1832A+B Problem(再升级)参与者 3已保存回复 10

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
10 条
当前快照
1 份
快照标识符
@m0qpfov1
此快照首次捕获于
2024/09/06 20:40
2 年前
此快照最后确认于
2025/11/04 21:39
4 个月前
查看原帖
已使用了背包求解,但发生了 RE 错误。
CPP
#include <cstdio>
#include <cstring>
const int N=1005;
int n,pointer,prime[N];
long long f[N];
bool isPrime[N];

void buildPrime(){
	for(int i=2;i<N;++i){
		isPrime[i]=true;
		for(int j=0;j<pointer;++j){
			if(i%prime[j]==0){
				isPrime[i]=false;
				break;
			}
		}
		if(isPrime[i]){
			prime[pointer++]=i;
		}
	}
}
void dp(){
//	for(int i=2;i<=n;++i){
//		for(int j=0;prime[j]<=i;++j){
//			f[i]+=f[i-prime[j]];
//		}
//	}
	for(int i=0;prime[i]<=n;++i){
		for(int j=0;prime[i]+j<=n;++j){
			f[prime[i]+j]+=f[j];
		}
	}
}
void init(){
	memset(f,0,sizeof(f));
	memset(prime,0,sizeof(prime));
	memset(isPrime,0,sizeof(isPrime));
}

int main(){
	init();
	f[0]=1;
	buildPrime();
	scanf("%d",&n);
	dp();
	printf("%lld",f[n]);
}

回复

10 条回复,欢迎继续交流。

正在加载回复...