题意：
给你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的节奏。
首先考量：
- $c_i$的定义，$c_i=2^i$。
- 分数获取的公式：$\mid{s_i-s_j}\mid$。
对于i<j<k。立刻可以得到以下特性：
- $\mid{s_k-s_j}\mid+\mid{s_j-s_i}\mid\geq\mid{s_k-s_i}\mid$
- $\mid{c_j-c_i}\mid<\mid{c_k-c_j}\mid<\mid{c_k-c_i}\mid$
进而我们可以立刻推论出：
- 一般的说，于其从i直接跳到k，不如经过j再到k。肯定时不会亏分数的。
- 对于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$的时候要特殊处理。
代码：
Submission #111283392 - Codeforces
Codeforces. Programming competitions and contests, programming community
