• 算法竞赛进阶指南 0x58 数据结构优化DP

    文章目录

    AcWing\295. 清理班次

    农民约翰正在指挥他的 N 头牛进行清理工作。他将一天划分为了 T 个班次（1∼T）。

    每头牛都只能在一天中的某一个时间段内进行不间断的工作。

    你需要帮助约翰排列出一个合理的奶牛的清理班次，使得每个班次都有奶牛在进行清理，而且动用的奶牛数量可以尽可能的少。

    输入格式

    第 1 行：两个空格隔开的整数 N 和 T。

    第 2…N+1 行：第 i+1 行包含两个整数，分别表示第 i 头牛可以进行工作的开始时间和结束时间。

    输出格式

    输出一个整数，表示在每个班次都有奶牛清理的情况下，所需的奶牛最小数量。

    如果无法做到每个班次都有奶牛清理，则输出 −1。

    数据范围

    1≤N≤25000,
    1≤T≤106

    输入样例：

    3 10
1 7
3 6
6 10

    • 1
    • 2
    • 3
    • 4

    输出样例：

    2

    • 1

    这道题目可以使用贪心的方法来做。但是对于下一道题目来说并不好拓展。

    这里使用动态规划

    状态表示：

    如果我把选择哪些奶牛做为转态，直接大乱！
    如果转态为f[i]表示覆盖 1~i 的区间，所需要的最少的奶牛数目，这样也是混乱，因为并不知道这些情况中区间覆盖的最右端究竟是在哪里。

    把第二种情况进行特殊化，就可以解决问题！

    f[i]表示已经覆盖 1~i 并且仅仅使用 i 左端的区间（排除了所有的右端点超过i的区间）。

    那么f[i]就等于以这一个点为右端点的所有区间(不妨记作 L-R )的min(f[k]) L − 1 ≤ K < R L-1\le K < R L−1≤K<R
    ***为什么是L-1？：***因为1~t，t+1~n也是可以覆盖1~n的

    在实际的情况下，并不需要完全枚举T，因为如果对于某一个i，不是以右端点结尾的，那么f[i]就是正无穷。

    所以仅仅需要按照R从小到大枚举N就行。

    由于涉及到两种操作，所以使用线段树解决！

    #include 
using namespace std;
const int N = 25006, T = 1e6+5;
const int INF = 0x3f3f3f3f;
int n, t;//n 表示总的奶牛数目，t表示有多少个时段
struct QAQ{
    int l, r;
    bool operator < (const QAQ &x)const{
        return r < x.r;
        //按照右端点的大小进行排序
        //因为如果是硬来的话，是从小到大枚举左端点
    }   
}a[N];

struct TREE{
    int l, r, ans;
}tr[T*4];//注意线段树的应该是4倍的。。。。。

int f[T];

void build(int p, int l, int r)
{
    tr[p].l = l, tr[p].r = r;
    tr[p].ans = INF;
    if(l == r) return ;
    int mid = (l+r)>>1;
    build(p*2, l, mid);
    build(p*2+1, mid+1, r);
}
void change(int p, int x, int v)
{
    if(tr[p].l == tr[p].r){
        tr[p].ans = v;
        return;
    }
    int mid = (tr[p].l+tr[p].r)>>1;
    if(x <= mid) change(p*2, x, v);
    else change(p*2+1, x, v);
    tr[p].ans = min(tr[p*2].ans, tr[p*2+1].ans);
}
int ask(int p, int l, int r)
{
    if(l <= tr[p].l && tr[p].r <= r)
    {
        return tr[p].ans;
    }
    int mid = (tr[p].l + tr[p].r) >> 1;
    int minn = INF;
    if(l <= mid) minn = min(ask(p*2, l, r), minn);
    if(r > mid) minn = min(minn, ask(p*2+1, l, r));
    return minn;
}

int main()
{
    scanf("%d%d", &n, &t);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d", &a[i].l, &a[i].r);
    }
    sort(a+1, a+n+1);
    build(1, 0, t);
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    change(1, 0, 0);
    for(int i = 1; i <= n; i++)
    {
        int last = ask(1, a[i].l-1, a[i].r-1);
        f[a[i].r] = min(f[a[i].r], last+1);
        change(1, a[i].r, f[a[i].r]);
    }
    if(f[t] == INF) puts("-1");
    else cout << f[t];
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75

    AcWing\296. 清理班次2

    农夫约翰雇佣他的 N 头奶牛帮他进行牛棚的清理工作。

    他将全天分为了很多个班次，其中第 M 个班次到第 E 个班次（包括这两个班次）之间必须都有牛进行清理.

    这 N 头牛中，第 i 头牛可以从第 a i a_i ai​个班次工作到第 b i b_i bi​个班次，同时，它会索取 c i c_i ci​ 的佣金。

    请你安排一个合理的清理班次，使得 [M,E] 时间段内都有奶牛在清理，并且所需支付给奶牛的报酬最少。

    输入格式

    第 1 行：包含三个整数 N，M 和 E。

    第 2…N+1 行：第 i+1 行包含三个整数 a i , b i , c i a_i,b_i,c_i ai​,bi​,ci​。

    输出格式

    输出一个整数，表示所需的最少佣金。

    如果无法做到在要求时间段内都有奶牛清理，则输出 −1。

    数据范围

    1≤N≤10000,
    0≤M,E≤86399,
    M≤ a i , b i a_i,b_i ai​,bi​≤E,
    0≤* c i c_i ci​*≤500000

    输入样例：

    3 0 4
0 2 3
3 4 2
0 0 1

    • 1
    • 2
    • 3
    • 4

    输出样例：

    5

    • 1

    如果知道上一道题目，那么这一道题目也就很水

    其他的全部不会变，仅仅需要将增加的参数转化为c而不是1.

    **值得注意：**INF：

    1. 自己定义的INF可能不是0x3f3f3f3f。
    2. int类型memset(arr, 0x3f, sizeof(arr))是0x3f3f3f3f。
    3. long long类型memset(arr, 0x3f, sizeof(arr))是0x3f3f3f3f3f3f3f3f。
    #include 
using namespace std;
typedef long long ll;
const int N = 25006, T = 1e6+5;
const long long INF = 0x3f3f3f3f3f3f3f3f;
int n, m, e;
struct QAQ{
    int l, r;
    long long c;
    bool operator < (const QAQ &x)const{
        return r < x.r;
    }   
}a[N];

struct TREE{
    ll l, r, ans;
}tr[T*4];

long long f[T];

void build(ll p, ll l, ll r)
{
    tr[p].l = l, tr[p].r = r;
    tr[p].ans = INF;
    if(l == r) return ;
    ll mid = (l+r)>>1;
    build(p*2, l, mid);
    build(p*2+1, mid+1, r);
}
void change(ll p, ll x, ll v)
{
    if(tr[p].l == tr[p].r){
        tr[p].ans = v;
        return;
    }
    ll mid = (tr[p].l+tr[p].r)>>1;
    if(x <= mid) change(p*2, x, v);
    else change(p*2+1, x, v);
    tr[p].ans = min(tr[p*2].ans, tr[p*2+1].ans);
}
ll ask(ll p, ll l, ll r)
{
    if(l <= tr[p].l && tr[p].r <= r)
    {
        return tr[p].ans;
    }
    ll mid = (tr[p].l + tr[p].r) >> 1;
    ll minn = INF;
    if(l <= mid) minn = min(ask(p*2, l, r), minn);
    if(r > mid) minn = min(minn, ask(p*2+1, l, r));
    return minn;
}

int main()
{
    scanf("%d%d%d", &n, &m, &e);
    m++, e++;
    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d%lld", &a[i].l, &a[i].r, &a[i].c);
        a[i].l++;
        a[i].r++;
    }
    sort(a+1, a+n+1);
    build(1, m - 1, e);
    memset(f, 0x3f, sizeof(f));
    f[m-1] = 0;
    change(1, m-1, 0);
    for(int i = 1; i <= n; i++)
    {
        long long last = ask(1, a[i].l-1, a[i].r-1);
        f[a[i].r] = min(f[a[i].r], last+a[i].c);
        change(1, a[i].r, f[a[i].r]);
    }
    if(f[e] == INF) puts("-1");
    else cout << f[e];
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78

    AcWing\297. 赤壁之战

    给定一个长度为 N 的序列 A，求 A 有多少个长度为 M 的严格递增子序列。

    输入格式

    第一行包含整数 T，表示共有 T 组测试数据。

    每组数据，第一行包含两个整数 N 和 M。

    第二行包含 N 个整数，表示完整的序列 A。

    输出格式

    每组数据输出一个结果，每个结果占一行。

    输出格式为 Case #x: y，x 为数据组别序号，从 1 开始，y 为结果。

    由于答案可能很大，请你输出对 109+7 取模后的结果。

    数据范围

    1≤T≤100,
    1≤M≤N≤1000,
    ∑T i=1N i×M i≤107
    序列中的整数的绝对值不超过109。

    输入样例

    2
3 2
1 2 3
3 2
3 2 1

    • 1
    • 2
    • 3
    • 4
    • 5

    输出样例

    Case #1: 3
Case #2: 0

    • 1
    • 2

    这一道题目的转态表示为f[i][j],
    表示已经考虑了1~i个数字，并且以第 i 个数字作为结尾的长度为 j 单调子序列。

    “并且以第 i 个数字作为结尾”必须添加，上升子序列与最后一个值有关，并且这样是为了唯一统计个数。

    状态转移：

    f[i][j] = ∑ k < i 且 a [ k ] < a [ i ] f [   i   ] [   j   ] \sum_{k∑k<i且a[k]<a[i]​f[ i ][ j ]

    如果要是暴力求解，那么就显然超时。

    可以考虑采用树状数组进行求解。
    BUT：值的范围太过于散，不便于直接开树状数组，所以要进行离散化。

    //注意：树状数组的0号元素的ask是0，并且无法修改！
#include 
using namespace std;
#define N 1010
int a[N];//存储原始的数值
int nums[N];//也是存储原始的数值，但是要作为离散化的工具
int tr[N];//树状数组
int f[N][N];
const int mod = 1e9+7;
inline int lowbit(int x)
{
    return x & -x;
}
void add(int x, int v, int maxx)
{
    for(; x <= maxx; x += lowbit(x))
        tr[x] = (tr[x]+v)%mod;
}
int ask(int x)
{
    int ans = 0;
    for(; x; x -= lowbit(x))
        ans = (ans + tr[x]) % mod;
    return ans;
}
int main()
{
    int T;
    scanf("%d", &T);
    for(int C = 1; C <= T; C++)
    {
        int cnt = 0;//注意：cnt仅仅用于离散化！
        int n, m;
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", a+i);
            nums[i] = a[i];
        }
        sort(nums+1, nums+1+n);
        cnt = unique(nums+1, nums+1+n)-(nums+1);//注意去重之后数组的大小已经发生了改变。
        for(int i = 1; i <= n; i++) a[i] = lower_bound(nums+1, nums+1+cnt, a[i]) - nums;
        //在二分的时候就应该是新的大小的数组。
        for(int i = 1; i <= n; i++)
        {
            f[i][1] = 1;
        }
        for(int j = 2; j <= m; j++)
        {
            for(int i = 1; i <= cnt; i++) tr[i] = 0;
            for(int i = 1; i <= n; i++)
            {
                f[i][j] = ask(a[i] - 1);
                add(a[i], f[i][j-1], cnt);
            }
        }
        int ans = 0; 
        for(int i = 1; i <= n; i++)
        {
            ans = (ans +f[i][m])%mod;
        }
        printf("Case #%d: %d\n", C, ans);
    }
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
  • 相关阅读:
    IPv6地址基础理论讲解
    KMP算法
    游戏数据分析必知必会
    算法与数据结构-Trie树
    MIT6.S081的gdb调试方法
    springboot+mybatis+thymeleaf实现简单的留言板
    SpringBoot 03: 常用web组件 - - - 拦截器 + Servlet + 过滤器
    Java23种设计模式之第三弹-工厂模式
    【css面试题】 实现一个盒子的水平竖直居中对齐效果
    大数据培训技术自定义Sink案例测试
  • 原文地址：https://blog.csdn.net/xjsc01/article/details/126083113