同求
by DarkKris @ 2016-11-16 19:18:53
我也想问这个问题，有谁不会可以看一看2065，与这题差不多；
by zxj200408 @ 2017-08-15 11:18:45
其实我一开始也想了好久，但后来觉得觉得是因为状态转移是由一个最优解获得另外一个最优解，如果不进行排序，有可能用来状态转移的数还并非是最优的解吧~
by Twilight_ @ 2017-09-09 19:29:30
不排序的话会产生后效性。因为这里时间，也就是先取走后取走会影响每个物品带来的价值
式子是这样的：
设在时间t,t+c带来的贡献是这样的
决定第i，j头猪的先后顺序。那么i在前和i在后带来的贡献分别是
$$
a\_i - p\_i \times t + a\_j - p\_j \times (t + c)
= a\_i - p\_i \times t + a\_j - p\_j \times t - c \times p\_j
$$
$$
a\_i - (t + c) \times p\_i + a\_j - p\_j \times t
= a\_i - p\_i \times t - c \times p\_i + a\_j - p\_j \times t
$$
我们要决定取的先后顺序，实际上只需要比较这两个式子的大小就行了
最后发现两个式子化为$-p_j$和$-p_i$，若前者大于后者，那么i在前，否则在后
实际上有这么一类排序贪心的题，这是很经典的问题了
by shadyqwq @ 2017-09-20 10:02:46