team2012-D3-2B

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

=== 0026 ===
{{{
对于每一场比赛，获胜的概率最高的10个对手是最优的选择，一共最多10场比赛，所以有效的对手最多10×10=100个
把这些有用的对手筛选出来之后，就可以进行dp
dp[i][mask]:目前10场比赛的状态为mask（1表示已经比过了，0表示还没比），目前选择第i个对手
    注意存储的是一个pair，第一关键字为全部获胜的概率，第二关键字为最高得分
决策有两种：一是跳过第i个对手，此时f[i+1][mask]=f[i][mask]
二是跟i打一场比赛，此时f[i+1][mask+1<<k] = max(f[i+1][new_mask], PDI(f[i][mask].first*p[k][i+1],f[i][mask].second+a[i+1]));
    其中k是选择打那一场比赛
}}}

=== 0027 ===
{{{
f[x][y][mask]: PII<turns, l> 走到(x,y)这个位置，当前Dominance 的状态为mask时，最小的回合数及其最小耗费的Mobility 
然后bfs即可
注意事件的优先级：
首先是Mobility 发生改变，当消耗的Mobility 达到l时要进入新一个回合，以及该位置被占领时Mobility变成0
然后再考虑是否能够消灭掉某个Dominance
}}}

=== 0030 ===
{{{
dp:
f[i][j]: 目前的时间为i，已经清醒了j个时间单位
然后分情况讨论：
1.第j+1个时间单位仍然清醒（要求 j < t + l）
    1.1 清醒但什么都不做
    1.2 参加一个event
2.第j+1个时间单位开始睡觉（要求 j >= t）
    此时注意因为多清醒了dt = j-t个时间单位，所以要睡k+dt = k + j - t个时间单位
    顺便减去dt^2
}}}

0026

对于每一场比赛，获胜的概率最高的10个对手是最优的选择，一共最多10场比赛，所以有效的对手最多10×10=100个
把这些有用的对手筛选出来之后，就可以进行dp
dp[i][mask]:目前10场比赛的状态为mask（1表示已经比过了，0表示还没比），目前选择第i个对手
    注意存储的是一个pair，第一关键字为全部获胜的概率，第二关键字为最高得分
决策有两种：一是跳过第i个对手，此时f[i+1][mask]=f[i][mask]
二是跟i打一场比赛，此时f[i+1][mask+1<<k] = max(f[i+1][new_mask], PDI(f[i][mask].first*p[k][i+1],f[i][mask].second+a[i+1]));
    其中k是选择打那一场比赛

0027

f[x][y][mask]: PII<turns, l> 走到(x,y)这个位置，当前Dominance 的状态为mask时，最小的回合数及其最小耗费的Mobility 
然后bfs即可
注意事件的优先级：
首先是Mobility 发生改变，当消耗的Mobility 达到l时要进入新一个回合，以及该位置被占领时Mobility变成0
然后再考虑是否能够消灭掉某个Dominance

0030

dp:
f[i][j]: 目前的时间为i，已经清醒了j个时间单位
然后分情况讨论：
1.第j+1个时间单位仍然清醒（要求 j < t + l）
    1.1 清醒但什么都不做
    1.2 参加一个event
2.第j+1个时间单位开始睡觉（要求 j >= t）
    此时注意因为多清醒了dt = j-t个时间单位，所以要睡k+dt = k + j - t个时间单位
    顺便减去dt^2