题解 P2008 【大朋友的数字】

kkksc03 · 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]。