2017-09-24 20:15:22
writer：pprp
题目链接：https://nanti.jisuanke.com/t/17319
题意：给你一串数，给你一个处理方法，确定出这串数的权值，然后让你在这串数中找到最长非下降子序列，并算出对应的权值和
这道题花费我时间最长了，我还是不是特别理解LIS找到的一些模板也不怎么会使用，各种错误，趁这次机会好好理解一下
代码如下：
//ac : L
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm> #define N 1000000+1000 using namespace std; int a[N];
int dp[N]; int binarySearch(int key,int l,int r)
{
while(l <= r)
{
int mid = (l + r)>>; if(key>=dp[mid] && key<=dp[mid+])
return mid;
else if(key>dp[mid])
l = mid+;
else
r = mid-;
}
return ;
} int main()
{
int ll = ;
int tmp;
while(cin >> tmp)
{
if(tmp < )
{}
else if(tmp >= )
{
for(int i=; i<; i++)
{
a[ll++] = tmp-;
}
}
else
{
a[ll++] = tmp;
}
} dp[]=a[]; //初始化
int len=;
for (int i=; i<ll; i++)
{
if (a[i]>=dp[len]) dp[++len]=a[i]; //如果可以接在len后面就接上
else //否则就找一个最该替换的替换掉
{
int j=upper_bound(dp+,dp+len+,a[i])-dp; //找到第一个大于它的d的下标
dp[j]=a[i];
}
} cout<<len<<endl; return ;
}
给我一个提示，可以简化题目，一开始想着弄成一个结构体，记录权值，但其实简化以后就直接用LIS就好了