传送门
思路
CF 的第一场 div3,在我提交了一份有错的代码后突然不能提交了,在跑什么 System Testing,我就跟它杠上了,直到它评测完。唉,我太弱了,这么傻逼的题都不能一次 AC,害得我正好碰到 System Testing,唉,我太弱啦!
离散化,设
fi
f
i
表示以
i
i
结尾的最长长度。如果存在 ai−1 就转移,否则就不转移。
参考代码
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef int INT_PUT;
INT_PUT readIn()
{
INT_PUT a = 0; bool positive = true;
char ch = getchar();
while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
if (ch == '-') { positive = false; ch = getchar(); }
while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
return positive ? -a : a;
}
void printOut(INT_PUT x)
{
char buffer[20]; int length = 0;
if (x < 0) putchar('-'); else x = -x;
do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
do putchar(buffer[--length]); while (length);
}
const int maxn = int(2e5) + 5;
int n;
int a[maxn];
int bound;
int disc[maxn];
void discretize()
{
for (int i = 1; i <= n; i++)
disc[++bound] = a[i];
std::sort(disc + 1, disc + 1 + bound);
bound = std::unique(disc + 1, disc + 1 + bound) - (disc + 1);
for (int i = 1; i <= n; i++)
a[i] = std::lower_bound(disc + 1, disc + 1 + bound, a[i]) - disc;
}
int f[maxn];
void run()
{
n = readIn();
for (int i = 1; i <= n; i++)
a[i] = readIn();
discretize();
int ans = 0;
int pos = 0;
for (int i = 1; i <= n; i++)
{
int t = std::lower_bound(disc + 1, disc + 1 + bound, disc[a[i]] - 1) - disc;
int val;
if (disc[t] != disc[a[i]] - 1)
val = 1;
else
val = f[t] + 1;
f[a[i]] = std::max(f[a[i]], val);
if (val > ans)
{
ans = val;
pos = i;
}
}
printOut(ans);
putchar('\n');
std::vector<int> rec;
int cnt = disc[a[pos]];
for (; pos; pos--)
{
if (disc[a[pos]] == cnt)
{
rec.push_back(pos);
cnt--;
}
}
for (int i = rec.size() - 1; ~i; i--)
{
printOut(rec[i]);
putchar(' ');
}
}
int main()
{
run();
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)