B-LIS & LCS

题目

东东有两个序列A和B。

他想要知道序列A的LIS和序列AB的LCS的长度。

注意，LIS为严格递增的，即a1<a2<…<ak(ai<=1,000,000,000)。

Input

第一行两个数n，m（1<=n<=5,000,1<=m<=5,000）

第二行n个数，表示序列A

第三行m个数，表示序列B

Output

输出一行数据ans1和ans2，分别代表序列A的LIS和序列AB的LCS的长度Simple Input

5 5

1 3 2 5 4

2 4 3 1 5

Simple Output

3 2

LIS呢，就是最长上升子序列，LCS就是最长公共子序列

在这里插入图片描述

那么如何解决本题呢，还是扒图，感觉有了PPT，世界开始变得美好了起来

在这里插入图片描述

第一个小题，求LIS还有二分法，可以把复杂度降为O(nlogn),具体怎么做，先不探讨，还是用O(n²)的算法做吧，orz

对于核心代码，写一个简单的例子，比如有一个序列
1 2 3 1 0 5 6 4 7 9 2
肯定最长的是1 2 3 5 6 7 9，也就是长度为7
数组f的变化过程为
f[1]=1;
f[2]=2;//因为a[2]>a[1]
f[3]=3;
因为发现a[4]<a[2],a[3],a[4]=a[1],所以if条件语句下的内容未被执行，所以mx=0
f[4]=1;
f[5]=1;//与f[4]的值同理可得
f[6]=4;//mx是不断max得来的，所以遍历至f[3]的时候，mx=3,mx>f[4],所以最后f[6]=4
f[7]=5;
f[8]=4;//因为前面的1 2 3都比4小
f[9]=6;
f[10]=7;
f[11]=2;

#include
   
    #include
    
     #define ll long longusing namespace std;const int maxn=1e4;ll a[maxn],b[maxn],f[maxn],f1[maxn][maxn],mx;int n,m;int main(){
    cin>>n>>m; for(int i=1;i<=n;i++)  cin>>a[i]; for(int i=1;i<=m;i++)  cin>>b[i]; f[1]=1; //最长上升子序列  for(int i=2;i<=n;i++){
   //核心代码，计算最长上升区间   mx=0;  for(int j=1;j

());//降序排序 cout<

C-拿数问题 II

YJQ 上完第10周的程序设计思维与实践后，想到一个绝妙的主意，他对拿数问题做了一点小修改，使得这道题变成了拿数问题 II。

给一个序列，里边有 n 个数，每一步能拿走一个数，比如拿第 i 个数， Ai = x，得到相应的分数 x，但拿掉这个 Ai 后，x+1 和 x-1 (如果有 Aj = x+1 或 Aj = x-1 存在) 就会变得不可拿（但是有 Aj = x 的话可以继续拿这个 x）。求最大分数。

本题和课上讲的有些许不一样，但是核心是一样，需要你自己思考。

Input

第一行包含一个整数 n (1 ≤ n ≤ 105)，表示数字里的元素的个数

第二行包含n个整数a1, a2, …, an (1 ≤ ai ≤ 105)

Output

输出一个整数：你能得到最大分值。

Example

Input

1 2

Output

Input

1 2 3

Output

Input

1 2 1 3 2 2 2 2 3

Output

Hint

对于第三个样例：先选任何一个值为2的元素，最后数组内剩下4个2。然后4次选择2，最终得到10分。

课上讲的拿数问题

在这里插入图片描述

本题的拿数问题与课上讲的拿数问题不一样就在于本题拿走了Ai=x,那么x-1和x+1不可拿,但是如果Ai-1 !=x-1(Ai-1 != x+1)的话，那么Ai-1还是可以拿的

本题解题过程：把输入的a[]中的数升序排序，用一个数组sum来记录每个数的个数
那么能拿到的最大分数的公式就是
dp[i]=max(dp[i-1],dp[i-2]+sum[i]*i）;//因为相同的可以拿，为了使分数最高，肯定要把一样的全拿呀。
然后就是继续举个例子说明
5 5 4 1 2 2 1 7 4 3
排序后：1 1 2 2 3 4 4 5 5 7
很明显，dp=22（其实一点也不明显
最大应该是dp[a[10]]=dp[7]=22，选择了1 1 3 5 5 7
dp[1]=2;//突然发现代码dp数组我好像忘记初始化？它可能开始就是0
dp[2]=4;
dp[3]=5;
dp[4]=12;
dp[5]=15;
dp[6]=15;//木有6,所以sum[6]=0，我可能也忘了初始化sum
dp[7]=22;

#include
   
    #include
    
     #define ll long longusing namespace std;const int maxn=1e5+10;ll a[maxn],n,f[maxn],sum[maxn];int main(){
    cin>>n; for(int i=1;i<=n;i++){
     cin>>a[i];  sum[a[i]]++; } sort(a+1,a+n+1,less
     
      ()); for(int i=a[1];i<=a[n];i++)//核心代码  f[i]=max(f[i-1],f[i-2]+sum[i]*i); cout<
      
       <