Longest Increasing Subsequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 189 Accepted Submission(s): 45
Problem Description
Bobo has a sequence a1,a2,…,an.
Let f(x) be the length of longest *strictly* increasing subsequence after replacing all the occurrence of 0 with x.
He would like to find ∑ni=1i⋅f(i).
Note that the length of longest strictly increasing subsequence of sequence s1,s2,…,sm is the largest k
such that there exists 1≤i1<i2<⋯<ik≤m satisfying si1<si2<⋯<sik.
Let f(x) be the length of longest *strictly* increasing subsequence after replacing all the occurrence of 0 with x.
He would like to find ∑ni=1i⋅f(i).
Note that the length of longest strictly increasing subsequence of sequence s1,s2,…,sm is the largest k
such that there exists 1≤i1<i2<⋯<ik≤m satisfying si1<si2<⋯<sik.
Input
The input consists of several test cases and is terminated by end-of-file.
The first line of each test case contains an integer n.
The second line contains n integers a1,a2,…,an.
The first line of each test case contains an integer n.
The second line contains n integers a1,a2,…,an.
Output
For each test case, print an integer which denotes the result.
## Constraint
* 1≤n≤105
* 0≤ai≤n
* The sum of n does not exceed 250,000.
## Constraint
* 1≤n≤105
* 0≤ai≤n
* The sum of n does not exceed 250,000.
Sample Input
2 1 1 3 1 0 3 6 4 0 6 1 0 3
Sample Output
3 14 49
Source
题意：
一个n个数的数列，f(i)表示将数列中所有的0替换成i之后数列的最长严格上升子序列的长度，求i*f(i)的和。
题解：
设不考虑0时原序列的LIS为L，设a[i],b[i]分别表示以点i结束和开始的LIS的长度,c[i]为原数列。
对每一个i，如果存在 i 的下一个0后面的j，满足a[i]+b[j]=L,那么替换掉0之后，LIS的长度为L+1，可以将0替换的范围时[c[i]+1,c[j]-1]，这是显而易见的。
具体实现时，我用O（n)的实现方法，虽然题目的数据没有卡其他方法，以防万一嘛。
首先，可以想到对于每一个i，要找的j一定在i的后方，这使我想到可以从后往前处理，用一个数组f[i]保存最长上升子序列长度为i的起始位置的数的最大值，因为这是所有满足要求的j的对应区间[c[i]+1,c[j]-1]的并。这样的话，每处理一个位置i，就更新f[i].
但还有一个问题，就是i与j之间必须至少要有一个0，我们如果边求区间，边更新f数组的话显然是错的（想一想为什么），怎么办？我用分段处理，每次处理相邻两个0之间的位置，处理完后再重新扫一遍，更新f数组。
还有就是区间的处理方法，当[a,b]为可取区间时，另开一个数组d，将d[a]++,d[b+1]--，然后到最后求前缀和，若d[i]为0，说明替换为数字i后LIS长度为L，反之为L+1。此题就完全解决了。
代码：
#include<bits/stdc++.h>
#define N 100010
#define LL long long
using namespace std;
const LL mod=1e9+7;
int a[N],b[N],c[N],f[N],d[N];
int main()
{
int n;
while (~scanf("%d",&n))
{
for (int i=0;i<=n;i++)a[i]=b[i]=d[i]=f[i]=0;
for (int i=1;i<=n;i++) scanf("%d",&c[i]);
int k=1;
while (c[k]==0 && k<=n) k++;
f[1]=c[k];int t=0;a[k]=1;
if (k<=n)t=1;
for (int i=k+1;i<=n;i++) if (c[i])
{
int j=lower_bound(f+1,f+t+1,c[i])-f;
f[j]=c[i];
a[i]=j; //end
if (j==t+1) t++;
}
k=n;
while (c[k]==0 && k) k--;
f[1]=-c[k];t=0; b[k]=1;
if (k>0)t=1;
for (int i=k-1;i>0;i--) if (c[i])
{
int j=lower_bound(f+1,f+t+1,-c[i])-f;
f[j]=-c[i];
b[i]=j; //begin
if (j==t+1) t++;
}
for (int i=0;i<=n;i++)f[i]=0;
k=n;
//f[0]=n+1;
while(k>0)
{
int y=k;
for (;k>0;k--)
{
if (!c[k]){f[0]=n+1;break;}
int u=t-a[k];
if (f[u]-1>c[k])
{
d[c[k]+1]++;
d[f[u]]--;
}
}
for (int i=y;i>k;i--) if (f[b[i]]<c[i]) f[b[i]]=c[i];
if (f[t]-1>c[k] && k)
{
d[c[k]+1]++;
d[f[t]]--;
}
k--;
}
for (int i=1;i<=n;i++) d[i]+=d[i-1];
LL ans=0;
for (int i=1;i<=n;i++)if (!d[i])ans+=(LL) i*(t);else ans+=(LL) i*(t+1);
printf("%I64d\n",ans);
}
}
京公网安备 11010502036488号