D题
题很好，感觉思维得到了升华。把整个题考虑成一个图，对每对$\{i, j\}$，只要tag[i] != tag[j]他们之间就要连边，边权为$|2^i-2^j|$。按照题意，需要找一条边权不断上升的、$\sum|s_i-s_j|$最大的路。由于边权不断上升，可以将边按边权排序（外层$i$从小到大，内层$j$从大到小），然后使用动态规划：dp[i][t]维护只使用前$t$条边时，终点为$i$的路的路径权值最大值。考虑转移，发现$t$增加$1$时只有至多两个dp值会发生变化，因为一步只引入了一条边，而且它只能被加在已经考虑过的路径的末尾。这样，我们可以舍弃$t$维度，而代之以时间维度：$dp$数组只有一维，dp[i]维护当前时刻以$i$结尾的路的路径权值最大值。每当时刻前进1，就新考虑一条边，更新一下dp[i]和dp[j]：$dp_i = \max(dp_i, dp_j + |s_i - s_j|)$和$dp_j=\max(dp_j, dp_i+|s_i-s_j|)$。