最长的递增子序列 Bobo学会了如何计算ICPCCamp中O（nlogn）中的最长增加子序列（LIS）。 对于那些没有加入ICPCCamp的人来说，召回LIS（a1，a2，…，an）被定义为f [1] 2⊕f [2] 2⊕???⊕f [n] 2其中⊕表示 异或（XOR）和f计算如下。 因为我在[1，2，…，n] 对于[1,2，…，i-1]中的j，f [i] = 1 如果a [j] <a [i]那么 f [i] = max（f [i]，f [j] 1） 给定序列A =（a1，a2，…，an），Bobo希望找到LIS（B1），LIS（B2），…，LIS（Bn），其中Bi是移除第i个 元素来自A. 输入 输入包含零个或多个测试用例，并由文件结束符终止。 对于每个测试用例： 第一行包含一个整数n。 第二行包含n个整数a1，a2，…，an。 ?2≤n≤5000 ?1≤ai≤n ?测试用例的数量不超过10个。 产量 对于每种情况，输出表示LIS（B1），LIS（B2），…，LIS（Bn）的n个整数。 示例输入 五 2 5 3 1 4 示例输出 5 13 0 8 0
Longest Increasing Subsequence Bobo learned how to compute Longest Increasing Subsequence (LIS) in O(nlogn) in ICPCCamp. For those who did not attend ICPCCamp as Bobo, recall LIS(a1,a2,…,an) is defined as f[1]2 ⊕ f[2]2 ⊕ ??? ⊕ f[n]2 where ⊕ denotes the exclusive-or (XOR) and f is calculated as follows. for i in [1, 2, …, n] f[i] = 1 for j in [1, 2, …, i - 1] if a[j] < a[i] then f[i] = max(f[i], f[j] 1) Given sequence A = (a1,a2,…,an), Bobo would like to find LIS(B1),LIS(B2),…,LIS(Bn) where Bi is the sequence after removing the i-th element from A. Input The input contains zero or more test cases and is terminated by end-of-file. For each test case: The first line contains an integer n. The second line contains n integers a1,a2,…,an. ? 2 ≤ n ≤ 5000 ? 1 ≤ ai ≤ n ? The number of test cases does not exceed 10. Output For each case, output n integers which denote LIS(B1),LIS(B2),…,LIS(Bn). Sample Input 5 2 5 3 1 4 Sample Output 5 13 0 8 0
思路：动态规划 最长递增子序列思想 先将 数字序列每个长度的最长的递增子序列长度找到 例如 1 2 3 4 5 (下标) a[i] 2 5 3 1 4 dp[i] 1 2 2 1 3 dp[i]代表当前序列长度 的最大递增子序列长度 （与导弹拦截一样） dp[1]=1 ( 2 ) dp[2]=2 (2,5) dp[3]=2 (2,3) dp[4]=1 ( 1 ) dp[5]=3 (2,3,4)
代码语言：javascript复制#include<stdio.h>
#include<string.h>
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
#define N 5002
int main()
{
int n,i,j;int a[N],dp[N],s[N];long long ans;
// s[i] i 代表 递增子序的长度 s[i]存 此长度最小的末元素的值
// 例如 s[2]=3 代表 长度为2 的增序末端值为 3
// 此题 长度2 有（2，5） （2，3）为撒s[2]=5不行 如果后面是 6 那么增序肯定变为3 但如果 4 就会有问题
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i )
scanf("%d",&a[i]);
for(i=1;i<=n;i ) //初始化 没删元素之前的 每个元素构成的子序列长度
{
dp[i]=1; //至少本身为 1
for(j=1;j<=i-1;j )
if(a[j]<a[i])
dp[i]=max(dp[i],dp[j] 1);
}
for(i=1;i<=n;i )//遍历要移除的序号
{
memset(s,10000,sizeof(s));
ans=0;
s[0]=0;
for(j=1;j<=i-1;j )//处理 移除序号 之前的 （移除序号值不影响之前的增序长度）
s[dp[j]]=min(s[dp[j]],a[j]), ans^=dp[j]*dp[j];
for(j=i 1;j<=n;j )//处理 移除序号 之后的
{
if(a[j]>s[dp[j]-1])// 当前序号处理的值 大于比这个序号的原本长度-1的最小值
s[dp[j]]=min(s[dp[j]],a[j]),ans^=dp[j]*dp[j]; //也就是说 移除元素不影响
else//否则 会影响 因此被影响的增序长度-1
s[dp[j]-1]=min(s[dp[j]-1],a[j]),ans^=(dp[j]-1)*(dp[j]-1);
}
if(i!=1)printf(" ");printf("%lld",ans);
}
printf("n");
}
return 0;
}
