描述
题解
LIS问题,但是并不简单啊,要求的不是长度,而是最长的出现的次数~~~我想了一天也没想通怎么搞,只是知道一定需要对LIS进行优化改造,渣爆了我。
找了大牛的代码看了看,看了许久,才略懂一二。
在求LIS时,用vector
开两个数组h[]和g[],h[i][j]
用来存储最长递增序列的第i个位置可以放的数字,对应g[i][j]
用来存储此时构成了多少个序列,然后通过二分查找h[i][k]
,找到对应的g[i][k]
,然后就可以获取这一段可以配成多少个序列,对这个值进行相关处理即可。
代码
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 50010;
const int MOD = 1e9 + 7;
inline int read()
{
int x = 0, c = getchar();
for (; c > '9' || c < '0'; c = getchar());
for (; c >= '0' && c <= '9'; c = getchar())
{
x = (x << 1) + (x << 3) + c - '0';
}
return x;
}
vector<int> h[MAXN];
vector<int> g[MAXN];
int f[MAXN]; // 递增序列
int maxLen, times;
inline int get(int c, int x)
{
int l = -1, r = (int)(h[c].size() - 1);
while (l < r - 1)
{
if (h[c][(l + r) >> 1] >= x)
{
l = (l + r) >> 1;
}
else
{
r = (l + r) >> 1;
}
}
l = (l >= 0) ? g[c][l] : 0;
return (g[c][g[c].size() - 1] + MOD - l) % MOD;
}
int main()
{
memset(f, 100, sizeof(f));
f[0] = -1;
h[0].push_back(-1);
g[0].push_back(1);
int n = read();
for (int k, x, s, i = 1; i <= n; i++)
{
k = read();
x = (int)(lower_bound(f, f + n + 1, k) - f);
f[x] = k;
h[x].push_back(k);
s = get(x - 1, k);
if (x > maxLen)
{
maxLen = x, times = 0;
}
if (x == maxLen)
{
times = (times + s) % MOD;
}
if (g[x].size())
{
s = (s + g[x][g[x].size() - 1]) % MOD;
}
g[x].push_back(s);
}
printf("%d\n", times);
return 0;
}