自动搬运

查看原文

来自洛谷，原作者为

	kkksc03 洛谷吉祥物 DA✩ZE

搬运于2025-08-24 21:32:53，当前版本为作者最后更新于2014-01-01 21:37:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题描述有些坑，不过读懂之后，我们会很容易得到一种算法。

看到这种题，一定能想到先建一个数组c，表示每个人的数字。先运用DP求出每个数字前的最长不下降子序列长度（第i个数的记为a[i]），然后再设置一个数组b，表示分数，很明显b[1]就是c[1]。然后对于每个数字i，枚举一下它前面的数字，一旦遇到一个数j，满足a[j]+1=a[i]，那么b[i]=b[j]+c[i]，然后跳出。

当然，程序最后还要确保：对于任何一个b[i]，都有b[i]<b[i+1]，违反的话b[i+1]=b[i]。