Codeforces Round #708 Genius DP

题意：

给你n道题。对于题目i，有一个$tag_i$，有一个分数$s_i$，以及一个难度$c_i$。其中$c_i=2^i$。

一开始，你可以任意选择一道题作为你第一道刷的题。且你的IQ为0。

从第一题之后，你刷的题j必须满足：$IQ<\mid{c_i-c_j}\mid$，且${tag_i}\neq{tag_j}$。之后你的IQ会变为$\mid{c_i-c_j}\mid$，并且获得$\mid{s_i-s_j}\mid$分。

问你能获得的最大分数。

题解：

这个题上来就提醒你注意内存限制只有32m。就是一脸要状压DP的节奏。

首先考量：

1. $c_i$的定义，$c_i=2^i$。
2. 分数获取的公式：$\mid{s_i-s_j}\mid$。

对于i<j<k。立刻可以得到以下特性：

1. $\mid{s_k-s_j}\mid+\mid{s_j-s_i}\mid\geq\mid{s_k-s_i}\mid$
2. $\mid{c_j-c_i}\mid<\mid{c_k-c_j}\mid<\mid{c_k-c_i}\mid$

进而我们可以立刻推论出：

1. 一般的说，于其从i直接跳到k，不如经过j再到k。肯定时不会亏分数的。
2. 对于j，如果我要去k，完全由理由往会到i先逛一圈，再去k。

于是dp就很显然了。定义dp[i][j]表示当考虑到第j道题时，以i结尾的最多的分数。
于是就有
$$dp[i][j]=\max(dp[i][j-1], dp[k][j-1]+\mid{s_j-s_k}\mid+\mid{s_j-s_i}\mid)\ (k\in[i+1,j-1])$$
其中k表示上一次以k结尾，这一次考虑到第j个问题，并且以问题i结尾。

然后如果tag重复就跳过。最后求最大值的时候小心不要$n^2$的扫，以及对dp[i][j]中的j进行状态压缩就完事了。最后还要注意$i=j$的时候要特殊处理。

代码：