洛谷P2008 大朋友的数字【DP-求LIS方案】

Date：2022.01.11
题意：n个数，求以每个数结尾的最长非下降子序列中每项的和，如果以一个数结尾的最长非下降子序列数量不止一个，取下标字典序最小的那一组加和。

思路：首先求出以每个数结尾的最长非下降子序列的长度 f [ i ] f[i] f[i]。
转移方程： f [ i ] = f [ j ] + 1 【 j ∈ [ 0 , i − 1 ] ∧ a [ i ] > = a [ j 】 f[i]=f[j]+1【jin[0,i-1] wedge a[i]>=a[j】 f[i]=f[j]+1【j∈[0,i−1]∧a[i]>=a[j】
其次，设以 i i i结尾的字典序最小的、最长非下降子序列各元素的和为 a n s [ i ] ans[i] ans[i]。找到每个 f [ i ] f[i] f[i]是由哪个 f [ j ] f[j] f[j]转移而来的，即找到每个 f [ i ] = = f [ j ] + 1 f[i]==f[j]+1 f[i]==f[j]+1中的 j j j，则以 i i i结尾的最长非下降子序列一定接在以 j j j结尾的最长非下降子序列的后面。
转移方程： a n s [ i ] = a n s [ j ] + a [ i ] 【 j ∈ [ 0 , i − 1 ] ∧ a [ i ] > = a [ j ] 】 ans[i]=ans[j]+a[i]【jin[0,i-1] wedge a[i]>=a[j]】 ans[i]=ans[j]+a[i]【j∈[0,i−1]∧a[i]>=a[j]】
注意：这里一定要有 a [ i ] > = a [ j ] a[i]>=a[j] a[i]>=a[j]，否则存在：1 2 5 3 4中 f [ 5 ] = = 4 f[5]==4 f[5]==4且 f [ 3 ] = = 3 f[3]==3 f[3]==3，但 a [ i ] < a [ j ] a[i]a[i] 代码如下：

#include 
#include 
#include 
using namespace std;
const int N = 2e5+10;
typedef long long LL;
LL n,m,t;
LL a[N],f[N],ans[N];
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) {cin>>a[i];ans[i]=a[i];}
    for(int i=1;i<=n;i++)
        for(int j=1;j=a[j]) f[i]=max(f[i],f[j]+1);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j=a[j]) {ans[i]=ans[j]+a[i];break;}
        cout<