算法提高 拿糖果 线性DP

     题目链接：拿糖果

   思路：首先给小于根号n的素数打表。d(i)表示当前剩余i颗糖，最多可以拿到多少糖。

    转移方程：d(i) = max(d(i), k + d(i - 2 * k))，此处k表示她可以从i颗糖中拿的糖数量，即k是素数并且i % k == 0。

    注意：妈妈可以拿的糖的数量如果不足P，则拿糖结束。

AC代码：

#include <cstdio>#include<cmath>#include <algorithm>#include <cstring>#include <utility>#include <string>#include <iostream>#include <map>#include <set>#include <vector>#include <queue>#include <stack>using namespace std;#define eps 1e-10#define inf 0x3f3f3f3f#define PI pair<int, int> const int maxn = 1e5 + 5;int vis[500], d[maxn];void init(int n) {	//vis[i] = 0表示是素数 	int m = sqrt(n + 0.5);	memset(vis, 0, sizeof(vis));	for(int i = 2; i <= m; ++i) if(!vis[i])		for(int j = i*i; j <= n; j += i) vis[j] = 1;}int dfs(int n) {	if(d[n]) return d[n];	if(n <= 3) return d[n] = 0;	int m = sqrt(n);	for(int i = 2; i <= m; ++i) {		if(!vis[i] && n % i == 0) { //质因数 			d[n] = max(d[n], i + dfs(n - 2*i));		}	}	return d[n];}int main() {	init(500);	int n;	while(scanf("%d", &n) == 1) {		memset(d, 0, sizeof(d));		PRintf("%d/n", dfs(n));	}	return 0;} 如有不当之处欢迎指出！