題目鏈接：拿糖果

   思路：首先給小于根號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;} 如有不當之處歡迎指出！