题目链接：点击打开链接
题意：
一个游戏由3个人轮流玩
每局游戏由当中一名玩家选择一个数字作为開始
目的：获得最小的得分
对于当前玩家 O 。面对 u 这个数字
则他的操作有：
1、 计分 u +1 ，然后 u++;
2、计分 u / x, 然后 u /= x; 当中x为u的因子且x为素数
然后下一个玩家继续上述操作
3个人各操作一次 为1轮
当一轮结束后，若u==1 则游戏结束
每一个人的得分为 他全部计分记录里最小的数字
若在一轮结束前 u就==1， 那么玩家的得分为本局游戏的初始数
求：
每一个人在採取最优操作下玩n局游戏的总得分（不同局得分相加）
输入n表示n局游戏
以下n行给定 人名缩写+u
表示哪个玩家開始，他选择了哪个数字
思路：
1、n局游戏之间各不影响，所以分开考虑每局游戏
2、对于一局游戏。则我们能够记忆化搜索出每一个数字u相应的状态
显然我们能够得到若u为素数时 答案就是 { 1, u, u}
若u不为素数，则u能够转移到状态v
在保证第一个数字最小的情况下，从越小的状态转移过来则结果越小
注意素数初始化时我们觉得是{prime, inf, inf} 这样会得到一些不存在状态，而不存在的状态意义是本局游戏的初值
#include <stdio.h>
#include <algorithm>
#include<iostream>
#include<string.h>
#include <math.h>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
#define N 100008
#define inf 100000000
#define ll int
ll prime[9599], primenum;
set<int>s;
void PRIME(ll Max_Prime){
primenum = 0;
prime[primenum++] = 2;
for(ll i = 3; i <= Max_Prime; i+= 2)
for(ll j = 0; j < primenum; j++)
if(i%prime[j]==0)break;
else if(prime[j] > sqrt((double)i) || j==primenum-1)
{
prime[primenum++] = i;
break;
}
}
struct node{
int a,b,c,ok;
node(int x=0,int y=0,int z=0,int yes=0):a(x),b(y),c(z),ok(yes){}
}dp[N];
void dfs(int u){
if(dp[u].ok)return;
int t, fir = inf, id = inf;
for(int i = 0; prime[i] <= u; i++)if(u % prime[i]==0) {
dfs(u/prime[i]);
t = min(u/prime[i], dp[u/prime[i]].c);
if(t < fir || (t == fir && u/prime[i] < id))
fir = t, id = u/prime[i];
}
dfs(u+1);
t = min(u+1, dp[u+1].c);
if(t < fir || (t == fir && u+1 < id))
fir = t, id = u+1;
dp[u] = node( fir, dp[id].a, dp[id].b, true);
}
int main(){
int i, n;
PRIME(100007);
s.clear();
for(i = 0; i < N; i++) dp[i].ok = false;
for(i = 0; i < primenum; i++) {
dp[prime[i]] = node(1, inf, inf, true);
s.insert(prime[i]);
}
dp[1] = node(1, 1, 1, true);
while(~scanf("%d",&n)){
node ans = node(0, 0, 0, true);
while(n--){
char ch[2]; int u;
scanf("%s %d", ch, &u);
dfs(u);
node tmp = dp[u];
if(tmp.a == inf) tmp.a = u;
if(tmp.b == inf) tmp.b = u;
if(tmp.c == inf) tmp.c = u; if(ch[0] == 'O')
ans.a += tmp.a, ans.b += tmp.b, ans.c += tmp.c;
else if(ch[0] == 'E')
ans.b += tmp.a, ans.c += tmp.b, ans.a += tmp.c;
else
ans.c += tmp.a, ans.a += tmp.b, ans.b += tmp.c;
}
printf("%d %d %d\n", ans.a,ans.b, ans.c);
}
return 0;
}