动态规划 专题

题目链接：蓝桥杯 ADV-205 拿糖果

题目描述

输入输出格式

数据规模和约定

N <= 100000

时空限制

  • 时间：1s
  • 空间：256MB

思路

先创建一个 素数表 ，然后直接 动态规划 ，递推式为：

dp[i] = max(dp[i], dp[i-2*prime[j]]+prime[j]);  //不拿第 i 块糖，或者拿第 i 块糖，取最大的糖果数

代码

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int dp[100000],flag[100000],prime[100000];
int cnt = 0;

void CreatePrime(){
	int len = sqrt(100000);
	for(int i = 2; i <= len; ++i){
		if(flag[i] == 0){  //是素数 
			prime[cnt++] = i;  //记录素数表 
			for(int j = i*i; j <= len; j=j+i){  //素数判断 
				flag[j] = 1;  //标记为不是素数 
			}
		}
	}
}

int main(){
	int n;
	scanf("%d",&n);
	CreatePrime();
	for(int i = 1; i <= n; ++i){
		for(int j = 0; j < cnt; ++j){
			if(prime[j] > sqrt(i)){  //当前素数大于根号下i 
				break;
			}
			if(i % prime[j] == 0){  //
				dp[i] = max(dp[i], dp[i-2*prime[j]]+prime[j]);
			}
		}
	}
	printf("%d\n",dp[n]);
	return 0; 
}