Solution
This problem remind you about the memory limitation at very begin. Normally, it's state compression DP.
Base on the problem:
- The definition of $c_i$: $c_i=2^i$。
- The definition of point: $\mid{s_i-s_j}\mid$。
For any $i<j<k$. We can get colusion below immediately：
- $\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$
Therefore, we can immediately deduce:
- Generally speaking, for $i<j<k$, rather than jump directly from i to k, it's better go through j and then to k.
- For $i<j<k$, if currently we are at j and the next step is k. It can back to i, and then move to k. (Base on the 2nd colusion above)
The the dp is very clear. let's define dp[i][j]: the max points for the first j questions which is end with ith question.
Then we have:
$$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 means: for first j-1 question which is end with question k.)
And just some tips:
- Skip it if the tag[i] and tag[k] is same.
- Need speical logic when $i=j$
- Don't forget comprese state.
Code:
Submission #111283392 - Codeforces
Codeforces. Programming competitions and contests, programming community
