深夜更一波啊。明天任务，分别A一道 二分，线性dp 和 搜索题
题目链接：https://www.luogu.com.cn/problem/P1020
大意：给出一组数据，求出这种数据的最长不升子序列 以及 至少多少个这样的不升子序列个数。
思路：前半个题最长不升子序列正常线性dp，后面求这样的不升子序列的个数，其实就是最长升子序列的个数，因为最长上升子序列包含 最长不升子序列的所有的逆序对。
这个题数据加强过了，n^2 dp只能过一半的数据。最优解法需要 二分dp。二分是我一个薄弱的地方（貌似我没什么强势的地方=.=）
那么这个题就需要我认真思考一下了。我发现了这个优化写法有两种。情况都挺复杂，但是大致的思想是一样的，就是我们的dp数组表示的不是当前i位置时所记录的符合的最大数量，而是直接记录的合法数，然后遇到不合法数进行替换，最后得到最长上升子序列的长度（但不一定是最长上升子序列）但是数量是和最长上升子序列的数量是一致的
50%code：d
#include<bits/stdc++.h>
using namespace std;
const int nn = 1e5+10;
int f[nn];
int dp[nn];
int a[nn];
//我们考虑 f[i]表示 到第i个数的时候，最长不升子序列的数量
int main()
{
int n=0;
while(~scanf("%d",&a[++n]));
--n;
// for(int i=1;i<=n;i++) cin>>a[i];
int maxt = 0;
for(int i=1;i<=n;i++)
{
f[i] = 1;
for(int j=1;j<i;j++)
if(a[i]<=a[j])
f[i] = max(f[i],f[j]+1);
maxt=max(maxt,f[i]);
}
cout<<maxt<<endl;
maxt = 0;
for(int i=1;i<=n;i++)
{
dp[i]=1;
for(int j=1;j<i;j++)
if(a[i]>a[j])
dp[i] = max(dp[i],dp[j]+1);
maxt=max(maxt,dp[i]);
}
cout<<maxt<<endl;
}
1.二分code：
我们每次都找一个合法的数移动到我们dp数组的最后，然后我们去找不合法的数，找到不合法的数之后，我们去前面合法的数去找一个合法的位置，然后覆盖掉。反复如此，因为我们放数的顺序是一致的，所以我们最后得出的答案数量自然也是正确的。有可能我们之后不合法的数放到了前面一个合法的位置，但最后这个数并不是我们所想要的合法数，而只是一个替代另一个序列的数。但是数量是一致的。
#include<bits/stdc++.h>
using namespace std;
const int nn = 1e5+10;
int f[nn];
int dp[nn];
int a[nn];
int main()
{
int n=0;
while(~scanf("%d",&a[++n]));
--n;
// for(int i=1;i<=n;i++) cin>>a[i];
int maxt = 0;
int cnt =1;
f[1] = a[1];
for(int i=2;i<=n;i++)
{
if(f[cnt]>=a[i])
f[++cnt] = a[i];//将符合条件的移到最后
else
for(int j=1;;j++)//找到不满足的，就找前面一个位置放进去。
if(f[j]<a[i]){f[j]=a[i];break;}
}
cout<<cnt<<endl;
cnt =1;
dp[1] = a[1];
for(int i=2;i<=n;i++)
{
if(dp[cnt]<a[i])
dp[++cnt] = a[i];
else
for(int j=1;;j++)
if(dp[j]>=a[i]){dp[j]=a[i];break;}
}
cout<<cnt<<endl;
}
2.二分code：
同上一样的原理，或者说这个是真正的二分。同样是记录数，我们这里记录的时候查找不合法数放置的位置是通过二分，利用已知合法数组的边界l和r，来控制二分的范围，然后如果遇到不合法数合法的位置，我们放进去，不同的是，这个放置的位置可能是合法的末尾，如果是合法的末尾，那么l+1的位置一定是maxt+1，也就是比maxt要大，这样我们就可以更新maxt。经过猜想和实验，我们将代码x>maxt替换成了x==maxt+1，同样AC。
#include<bits/stdc++.h>
using namespace std;
const int nn = 1e5+10;
int f[nn];
int dp[nn];
int a[nn];
int main()
{
int n=0;
while(~scanf("%d",&a[++n]));
--n;
// for(int i=1;i<=n;i++) cin>>a[i];
int maxt = 0;
f[0] = 0x3f3f3f3f;
for(int i=1;i<=n;i++)
{
int l = 0, r = maxt+1;//用来控制合法数组的l和r
while(r-l>1)
{
int m = l+(r-l)/2;
if(f[m]>=a[i]) l=m; else r=m; //从我们已知的合法数中去寻找，求得合法位置放置此数。
} //同样是覆盖的原理，同上一种二分。或者说这次我们找的是真正的二分，而上一个是暴力的放置数。
int x = l+1;
if(x>maxt) maxt = x;//如果新得到的更大，也就是说它是一个新的合法数，我们更新maxt，然后放置到最后
f[x] = a[i];
}
cout<<maxt<<endl;
maxt = 0;
dp[0] = 0;
for(int i=1;i<=n;i++)
{
int l = 0, r = maxt+1;
while(r-l>1)
{
int m = l+(r-l)/2;
if(dp[m]<a[i]) l=m; else r=m;
}
int x = l+1;
if(x>maxt) maxt = x;
dp[x] = a[i];
}
cout<<maxt<<endl;
}