Algorithms for LIS

DP

int LIS(vector<int> nums) {
int n = nums.size();
int dp[n];
int res = 0;
for (int i = 0; i < n; ++ i) {
dp[n] = 1;
for (int j = 0; j < i; ++ j) {
if (nums[j] < nums[i])
dp[i] = max(dp[i], dp[j] + 1);
}
res = max(res, dp[i]);
}
return res;
}


Sort + LCS

int LCS(vector<int> a, vector<int> b) {
assert(a.size() == b.size());

int n = a.size();
int dp[n + 1][n + 1];
for (int i = 0; i < n; ++ i) {
for (int j = 0; j < n; ++ j) {
if (i == 0 || j == 0)
dp[i][j] = 0;
else if (a[i - 1] == b[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[n][n];
}

int LIS(vector<int> nums) {
auto sorted = nums;
sort(sorted.begin(), sorted.end());
return LCS(nums, sorted);
}


DP + BS

int LIS(vector<int> nums) {
vector<int> dp;
for (auto n : nums) {
auto it = lower_bound(dp.begin(), dp.end(), n);
if (it == dp.end()) dp.push_back(n);
else *it = n;
}
return dp.size();
}


AtCoder Grand Contest 019C

In the city of Nevermore, there are 10e8 streets and 10e8 avenues, both numbered from 0 to 10e8 − 1. All streets run straight from west to east, and all avenues run straight from south to north. The distance between neighboring streets and between neighboring avenues is exactly 100 meters. Every street intersects every avenue. Every intersection can be described by pair (x,y), where x is avenue ID and y is street ID.

There are N fountains in the city, situated at intersections (Xi,Yi). Unlike normal intersections, there’s a circle with radius 10 meters centered at the intersection, and there are no road parts inside this circle. The picture below shows an example of how a part of the city with roads and fountains may look like.

• 0≤x1,y1,x2,y2<10e8
• 1≤N≤200,000
• 0≤Xi,Yi<10e8
• Xi≠Xj for i≠j
• Yi≠Yj for i≠j
• Intersections (x1,y1) and (x2,y2) are different and don’t contain fountains.
• All input values are integers.

x1 y1 x2 y2 N X1 Y1 X2 Y2 : XN YN

Print the shortest possible distance one needs to cover in order to get from intersection (x1,y1) to intersection (x2,y2), in meters. Your answer will be considered correct if its absolute or relative error doesn’t exceed 10e−11.

Samples:

I: 1 1 6 5 3 3 2 5 3 2 4

O: 891.415926535897938

I: 3 5 6 4 3 3 2 5 3 2 4

O: 400.000000000000000

I: 4 2 2 2 3 3 2 5 3 2 4

O: 211.415926535897938

Ok，一个网格给定两个点，那么不考虑喷泉的走法是固定的，长度为 abs(x1 - x2) + abs(y1 - y2)。

1. k <= c, 那么就一定有一种走法，使得我们经过这个子序列中每个温泉的时候都是转角
2. k == c + 1，那么一定存在一个喷泉需要经过，所以走法是走c个角，并经过剩余的一个。

#include <bits/stdc++.h>

using namespace std;

pair<long long, long long> p[200000];

const double PI = 3.14159265358979323846;
const double R = 10.0;
const double quarter_circle = PI * R / 2;
const double edge = 100.0;

using PLL = pair<long long, long long>;
int dp[200000];

int main() {
long long x1, y1, x2, y2;
scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);

if (x1 > x2) {
swap(x1, x2);
swap(y1, y2);
}

long long y_min = min(y1, y2), y_max = max(y1, y2);

// drop those not used
int n;
scanf("%d", &n);
for (int i = 0; i < n;) {
scanf("%lld %lld", &p[i].first, &p[i].second);
if (p[i].first < x1 || p[i].first > x2 || p[i].second < y_min || p[i].second > y_max) {
n--;
} else {
++i;
}
}

// x1 <= x2
double res = edge * (x2 - x1 + y_max - y_min);
sort(p, p + n, [&](const PLL& a, const PLL& b) { return a.first < b.first; });
if (y1 > y2) {
for (int i = 0; i < n; ++i) {
p[i].second = -p[i].second;
}
}

int len = 0;
for (int i = 0; i < n; ++i) {
auto it = lower_bound(dp, dp + len, p[i].second);
*it = p[i].second;
if (it == dp + len) {
len ++;
}
}

int max_corner = min(x2 - x1, y_max - y_min);

if (len < max_corner + 1)
res += len * (quarter_circle - 2 * R);
else
res += max_corner * (quarter_circle - 2 * R) + (2 * quarter_circle - 2 * R);

printf("%.15f\n", res);

return 0;
}