ACM 省赛E题 最长的递增子序列（动态规划+最长递增子序列）--------C语言—菜鸟级

最长的递增子序列
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)

#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;
}

  

 

  
 
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
 

文章来源: fivecc.blog.csdn.net，作者：Five-菜鸟级，版权归原作者所有，如需转载，请联系作者。

原文链接：fivecc.blog.csdn.net/article/details/80258543