看上去相似的题目解法却千差万别

懵逼的 题目

传送至 Codevs

扯淡的 题解

第一题贪心, 和第三题一样 只不过数据范围不同…
第二题序列DP 我沙茶的写成了离散化 × 背包
第四题和第二题一样 序列DP 只不过数据范围不一样
第五题离散化 × 序列DP

  • 贪心就是给右端点排序, 然后枚举线段, 能放就放
  • DP 就是, f[i] 代表坐标为 0 ~ i 能取到的最大的价值, f[i] = f[i - 1]; f[i] = max(f[i], f[当前线段的右端点] + 当前线段的价值);

没了…是不是很水?

沙茶的 代码

//线段覆盖 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define INF (999)
#define MAXN (100 + 5)
using namespace std;
struct xd
{
    int lx;
    int rx;
}a[MAXN];
int n;
int ans;
bool cmp(xd, xd);
void tx();
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &a[i].lx, &a[i].rx);
        if (a[i].lx > a[i].rx)
        swap(a[i].lx, a[i].rx);
    }
    tx();
    printf("%d", ans);
}
void tx()
{
    sort(a + 1, a + n + 1, cmp);
    int dqr = -INF + 1;
    for (int i  = 1; i <= n; i++)
    {
        if (a[i].lx >= dqr && a[i].rx < INF)
        {
            dqr = a[i].rx;
            ans++;
        }
    }
}
bool cmp(xd x, xd y)
{
    return x.rx < y.rx;
}
//线段覆盖2 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define INF (1000000)
#define MAXN (2000 + 5)
using namespace std;
struct lsh
{
    int zhi;
    int belong;
    bool lorr;
}b[MAXN * 2];
struct xd
{
    int l;
    int r;
    int c;
}a[MAXN];
int n;
int g[MAXN][MAXN];
int f[MAXN * 2];// f[i] 代表以i为结尾的序列的最大价值 
void init();
bool cmp(lsh, lsh);
void dp();
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].c);
        b[i].zhi = a[i].l;    b[i + n].zhi = a[i].r;    
        b[i + n].belong = b[i].belong = i;
        b[i].lorr = false;    b[i + n].lorr = true;
    }
    init();
    /*for (int i = 1; i <= n; i++)
    {
        printf("%d %d %d\n", a[i].l, a[i].r, a[i].c);
    }*/
    dp();
    printf("%d", f[2 * n]);
    return 0;
}
bool cmp(lsh x, lsh y)
{
    return x.zhi < y.zhi;
}
void init()
{
    sort(b + 1, b + n + n + 1, cmp);
    int zb = 0;
    for (int i = 1; i <= n + n; i++)
    {
         if (b[i].lorr)
         {
             a[b[i].belong].r = zb;
         }
         else
         {
             a[b[i].belong].l = zb;
         }
         if (b[i].zhi != b[i + 1].zhi)
             zb++;
    }
    memset(g, 0, sizeof(g));
    for (int i = 1; i <= n; i++)
    {
        if (!g[a[i].l][a[i].r])
        {
            g[a[i].l][a[i].r] = i;
        }
        else
        {
            if (a[i].c > a[g[a[i].l][a[i].r]].c)
            {
                g[a[i].l][a[i].r] = i;
            }
        }
    }
}
void dp()
{
    memset(f, 0, sizeof(f));
    for (int i = 0; i <= n + n; i++)
    {
        if (i - 1 >= 0)
        f[i] = f[i  - 1];
        for (int j = 0; j <= i; j++)
        {
            if (g[j][i])
            {
                f[i] = max(f[i], f[j] + a[g[j][i]].c);
            }
        }
    }
}
/*
10
0 3 4
1 4 7
15 19 8
1 2 6
1 3 4
2 5 6
4 7 7
2 4 3
3 8 10
7 12 2
*/
//线段覆盖3 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define INF (1000000 + 5)
#define MAXN (1000000 + 5)
using namespace std;
struct xd
{
    int lx;
    int rx;
}a[MAXN];
int n;
int ans;
bool cmp(xd, xd);
void tx();
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &a[i].lx, &a[i].rx);
        if (a[i].lx > a[i].rx)
        swap(a[i].lx, a[i].rx);
    }
    tx();
    printf("%d", ans);
}
void tx()
{
    sort(a + 1, a + n + 1, cmp);
    int dqr = -INF + 1;
    for (int i  = 1; i <= n; i++)
    {
        if (a[i].lx >= dqr && a[i].rx < INF)
        {
            dqr = a[i].rx;
            ans++;
        }
    }
}
bool cmp(xd x, xd y)
{
    return x.rx < y.rx;
}
//线段覆盖4 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define MAXN (1000000 + 5)
#define INF (1000000)
#define LL long long
using namespace std;
struct xd 
{
    int lside;
    int weight;
    xd(int l, int w): lside(l), weight(w) {}
};
vector <xd> lx[INF + 5];
int n;
LL f[MAXN];
void dp();
int main()
{
    scanf("%d", &n);
    int srx, sry, src;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d%d", &srx, &sry, &src);
        lx[sry].push_back(xd(srx, src));
    }
    dp();
    printf("%lld", f[INF]);
    return 0;
}
void dp()
{
    f[0] = 0;
    for (int i = 0; i <= INF; i++)
    {
        if (i - 1 >= 0)
        f[i] = f[i - 1];
        for (int j = 0; j < lx[i].size(); j++)
        {
            f[i] = max(f[i], (LL)f[lx[i][j].lside] + lx[i][j].weight);
        }
    }
}
//线段覆盖5 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define LL long long
#define INF (2000000)
#define MAXN (1000000 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
using namespace std;
struct cxd
{
    LL lside;
    LL rside;
    int weight;
}a[MAXN];
struct xd
{
    int lside;
    int weight;
    xd(int l, int w): lside(l), weight(w)    {}
};
struct node
{
    LL zb;
    int belong;
    bool is_left;
}c[MAXN * 2];
int n;
LL f[INF + 5];
vector <xd> lx[INF];
void dp();
void init();
bool cmp(node, node);
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld%lld%d", &a[i].lside, &a[i].rside, &a[i].weight);
        c[i].belong = c[i + n].belong = i;
        c[i].zb = a[i].lside;    c[i + n].zb = a[i].rside;
        c[i].is_left = true;    c[i + n].is_left = false;
    }
    init();
    dp();
    printf("%lld", f[INF]);
    return 0;
}
bool cmp(node x, node y)
{
    return x.zb < y.zb;
}
void init()
{
    sort(c + 1, c + n + n + 1, cmp);
    int cnt = 1;
    for (int i = 1; i <= n + n; i++)
    {
        if (c[i].is_left)
            a[c[i].belong].lside = cnt;
        else
            a[c[i].belong].rside = cnt;
        if (c[i].zb != c[i + 1].zb)
        ++cnt;
    }
    for (int i = 1; i <= n; i++)
    {
        lx[a[i].rside].push_back(xd(a[i].lside, a[i].weight));
    }
}
void dp()
{
    f[0] = 0;
    for (int i = 1; i <= INF; i++)
    {
        f[i] = f[i - 1];
        for (int j = 0; j < lx[i].size(); j++)
        {
            f[i] = max(f[i], (LL)f[lx[i][j].lside] + lx[i][j].weight);
        }
    }
}

By 文化课爆炸的 Cansult