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$的时候要特殊处理。

代码:

Submission #111283392 - Codeforces
Codeforces. Programming competitions and contests, programming community