Codeforces960F - Pathwalks + 最长不下降子序列(LIS)选讲

首先先来吐槽一下这场比赛,简直就是我第一次要么 WA 1 或者就是 WA 35+ 的一场比赛,也不知道出题人怎么这么流比

• • LIS
  • Codeforces 960F

LIS

LIS背景:$LIS背景:$
给你一个序列 a 让你选出最长的子序列,使得每一个元素 a′i+1>=a′i$a_{i+1}^{\prime }>=a_i^{\prime }$

样例

input:
7
2 5 3 4 1 7 6
output:
4(注释: 选择 2 3 4 6)

考虑最朴素的 n2$n^2$ 做法,其实就是我们设fi$f_i$为 必须以 ai$a_i$ 结尾的LIS$LIS$ 的最长长度

于是我们有了DP方程:

fi=max∑j=1i−1[aj<ai]∗f[j]+1(求和指的就是暴力枚举,不是"求和")$$f_i=max\sum _{j=1}^{i-1}[a_j<a_i]\ast f[j]+1(求和指的就是暴力枚举,不是"求和")$$

但是很容易想到我们也可以二分找出答案对吧!
于是nlogn$nlo{g}_n$算法奉上

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=10000005;
int a[N];
int d[N];

int main()
{
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    if (n==0)  //0个元素特判一下 
    {
        printf("0\n");
        return 0;
    }
    d[1]=a[1];  //初始化 
    int len=1;
    for (int i=2;i<=n;i++)
    {
        if (a[i]>=d[len]) d[++len]=a[i];  //如果可以接在len后面就接上 
        else  //否则就找一个最该替换的替换掉 
        {
            int j=upper_bound(d+1,d+len+1,a[i])-d;  //找到第一个大于它的d的下标 
            d[j]=a[i]; 
        }
    }
    printf("%d\n",len);    
    return 0;
}

Codeforces 960F

题意:

有一张有向图,按照顺序输入,让你求连续的一条路径,使得边的输入顺序递增而且权值也是递增的,输出路径的长度!

分析:

此题我们可以快速想到一个复杂度较大的DP方程(所有算法都是优化而来的嘛)
我们用

f[i][j]表示i节点结尾的路径最长的边权值不超过j的答案$$f[i][j]表示i节点结尾的路径最长的边权值不超过j的答案$$

每一次输入一条有向边u−>v权值为w$u->v权值为w$
都有

fv,w=(fv,i,fu,w−1+1)同理依次更新f[v][w−1e5]$$f_{v,w}=(f_{v,i},f_{u,w-1}+1)同理依次更新f[v][w-1e5]$$

但是我们会发现和LIS 其实非常的像对吧,于是我们f$f$ 数组用map来维护一下就好了

代码:

#pragma GCC optimize(2)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#define N 100005
#define R register
using namespace std;

int n, m, ans, u, v, w;
map<int, int> C[N];

inline int max(int x, int y)
{
    return (x > y) ? x : y;
}
inline int lowbit(int x)
{
    return x & (-x);
}
inline int query(int x, int y)
{
    int res = 0;
    for(R int i = y; i > 0; i -= lowbit(i))
        res = max(res, C[x][i]);
    return res;
}
inline void update(int x, int y, int val)
{
    for(R int i = y; i < N; i += lowbit(i))
        C[x][i] = max(C[x][i], val);
}
int main()
{
    scanf("%d%d", &n, &m);
    for(R int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &u, &v, &w);
        w++;
        update(v, w, query(u, w - 1) + 1);
    }
    for(R int i = 1; i <= n; i++)
    {
        ans = max(ans, query(i, N - 4));
    }
    printf("%d\n", ans);
    return 0;
}