• 算法竞赛进阶指南 0x57 倍增优化DP

    文章目录

    前方高能！！！

    总论

    可以使用倍增的情况是这一种情况可以任意划分。

    image

    AcWing\293. 开车旅行

    image
    image
    image

    输入样例：

    10
4 5 6 1 2 3 7 8 9 10
7
10
1 7
2 7
3 7
4 7
5 7
6 7
7 7
8 7
9 7
10 7

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    输出样例：

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    这一道题目真的是难中难！！！

    注意题目中所说的“且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市 i 的海拔高度为 H i H_i Hi​。”.注意这些城市并不是排列在同一条线上，可能是1号到3号的距离更近。但是总体上的趋势是往东走。

    现在思考，对于每一个点，都会向东走，走到距离最小或者是最小的地方。

    由于：

    1. 各个城市的海拔高度互不相同
    2. 当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近

    所以每一个点（无论是A开车还是B开车）到达的下一个点的位置是固定的。SO？如果确定了起始点，那么所走的路线是唯一固定的。

    part1 确定ga[], gb[]

    由于最大值与最小值是在目前所处的点的东方，所以遍历的时候从右向左。遍历完一个就加上值。

    使用set来求邻值。

    对set的使用方法进行分析：

    image

    邻值肯定在与当前值最近的地方。如果最近的是2，那么次近的就是1或者3. 反之，如果最近的是3，那么次近的是2或者4.

    所以只需要关注离他最近的这是个值。

    为了方便，可以在set中存入两个正无穷以及两个负无穷！
    注意：由于set不能含有相同的元素，所以两个“正无穷”不能相等

    注意：0x3f3f3f3f不一定可以代表正无穷！他的值是1,061,109,567，大概是 1 0 9 10^9 109，当可能存在的最大值大于 1 0 9 10^9 109时，应该选择其他最大值，甚至是选择long long。

    part2 确定f[]

    对于f[]的确定，代码不是太难，重点是要学会使用倍增求出。

    f[i][j][k]表示从j出发，k先开车，走过 2 i 2^i 2i所到达的位置。
    k == 0表示小A开车

    1. 显然f[0][j][0] = ga[j]，f[0][j][1] = gb[j]
    2. 当j==1，有**(注意：与3不同的原因是 2 1 2^1 21的一半不再是偶数，初始开车的人不同)**
      f[1][j][0] = f[0][ f[0][j][0] ][1]（先小A开一下，然后小B在小A开到的位置继续开。
      f[1][j][1] = f[0][ f[0][j][1] ][0]
    3. 当j > 1，有
      f[i][j][0] = f[i-1][ f[i-1][j][0] ][0]
      f[i][j][1] = f[i-1][ f[i-1][j][1] ][1]

    f 的第一维的确定：由于使用倍增。而 2 16 = 65 , 536 2^{16} =65,536 216=65,536所以17已经够使用。

    part3 确定da[]和db[]

    同样需要找到转移关系。

    da[i][j][k]表示从j出发，k先开车，走过 2 i 2^i 2i，小A所走过的所有距离。
    db[i][j][k]表示从j出发，k先开车，走过 2 i 2^i 2i，小B所走过的所有距离。

    与上面相同，分为以下三种情况：

    1. da[0][j][0] = dist(j, f[0][j][0]), db[0][j][0] = 0
      db[0][j][1] = dist(j, f[0][j][1]), da[0][j][1] = 0
    2. 当i == 1有：
      da[1][j][k] = da[0][j][k] + da[0][ f[0][j][k] ][1-k]
      db[1][j][k] = db[0][j][k] + db[0][ f[0][j][k] ][1-k]
    3. 当i > 1，有：
      da[i][j][k] = da[i-1][j][k] + da[i-1][ f[i-1][j][k] ][k]
      db[i][j][k] = db[i-1][j][k] + db[i-1][ f[i-1][j][k] ][k]
    #include 
using namespace std;
const int N = 1e5+5, M = 17;
const long long INF = 1e12;
long long h[N];
typedef long long ll;
typedef pair<ll, int> PLI;
set<pair<ll, int> >s;
ll ga[N], gb[N];
int f[M][N][2];
ll da[M][N][2];
ll db[M][N][2];
void init_g(int n)
{
    s.insert(make_pair(INF, 0));
    s.insert(make_pair(INF+1, 0));
    s.insert(make_pair(-INF, 0));
    s.insert(make_pair(-INF-1, 0));
    for(int i = n; i; i--)
    {
        vector<PLI>v;
        set<pair<ll, int> >::iterator it = s.lower_bound(make_pair(h[i], i));
        it++;
        for(int j = 1; j <= 4; j++) {
            v.push_back(*it);
            it--;
        }
        ll pmin1 = 0, pmin2 = 0;
        ll min1 = INF, min2 = INF;
        for(int j = 3; j >= 0; j--)
        {
            ll val = abs(v[j].first-h[i]);
            ll pos = v[j].second;
            if(val < min1)
            {
                min2 = min1;
                pmin2 = pmin1;
                min1 = val;
                pmin1 = pos;
            }
            else if(val < min2)
            {
                min2 = val;
                pmin2 = pos;
            }
        }
        ga[i] = pmin2, gb[i] = pmin1;//注意可能最后ga[n-1],ga[n],gb[n-1],gb[n]存在问题
        s.insert(make_pair((ll)h[i], i));
    }
}
void init_f(int n)
{
    for(int i = 0; i < M; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(i == 0)
            {
                f[0][j][0] = ga[j];
                f[0][j][1] = gb[j];
            }
            else if(i == 1)
            {
                f[1][j][0] = f[0][ f[0][j][0] ][1];
                f[1][j][1] = f[0][ f[0][j][1] ][0];
            }
            else
            {
                f[i][j][0] = f[i-1][ f[i-1][j][0] ][0];
                f[i][j][1] = f[i-1][ f[i-1][j][1] ][1];   
            }
            
        }
    }
}
inline ll dist(ll a, ll b)
{
    return abs(h[a]-h[b]);
}
void init_d(int n)
{
    for(int i = 0; i < M; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(i == 0)
            {
                da[0][j][0] = dist(j, f[0][j][0]), db[0][j][0] = 0;
                db[0][j][1] = dist(j, f[0][j][1]), da[0][j][1] = 0;
            }
            else
            {
                for(int k = 0; k < 2; k++)
                {
                    if(i == 1)
                    {
                        da[1][j][k] = da[0][j][k] + da[0][ f[0][j][k] ][1-k];
                        db[1][j][k] = db[0][j][k] + db[0][ f[0][j][k] ][1-k];
                    }
                    else{
                        da[i][j][k] = da[i-1][j][k] + da[i-1][ f[i-1][j][k] ][k];
                        db[i][j][k] = db[i-1][j][k] + db[i-1][ f[i-1][j][k] ][k];
                    }
                }
            }
        }
    }
}
void calc(ll p, ll x, ll &a, ll &b)
{
    a = 0, b = 0;
    for(int i = M-1; i >= 0; i--)
    {
        if(f[i][p][0] && a+b+da[i][p][0]+db[i][p][0] <= x)//从小A开始走
        {
            a += da[i][p][0];
            b += db[i][p][0];
            p = f[i][p][0];
        }
    }
}
int main()
{

    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%lld", h+i);
    init_g(n);
    //for(int i = 1; i <= n; i++)
    //    cout << ga[i] << " " << gb[i] << "\n";
    init_f(n);
    init_d(n);
    int x0;
    int res = 0;
    ll h_max = 0;
    double rate_min = INF;//GUG位置：用了ll 。。。。。
    scanf("%d", &x0);
    for(int i = 1; i <= n; i++)
    {
        ll aa, bb;
        calc(i, x0, aa, bb);
        double rate = bb?(double)aa/bb :INF;
        if(rate < rate_min || rate == rate_min &&h[i] > h_max)
        {
            rate_min = rate;
            res = i;
            h_max = h[i];
        }
    }
    printf("%lld\n", res);
    int m;
    scanf("%d", &m);
    while(m--)
    {
        ll s, x;
        cin >> s >> x;
        ll aa, bb;
        calc(s, x, aa, bb);
        printf("%d %d\n", aa, bb);
    }
    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
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163

    AcWing\294. 计算重复

    image

    输入样例：

    ab 2
acb 4
acb 1
acb 1
aa 1
aaa 3
baab 1
baba 11
aaaaa 1
aaa 20

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    输出样例：

    2
1
4
7
12

    • 1
    • 2
    • 3
    • 4
    • 5

    这一道题目简单概括就是求一个最大的m，使得字符串s2被复制m*n2之后是字符串s1*n1的子序列。

    更进一步进行简化：可以认为求一个最大的t，使得s2复制t次后是s1复制n1次的子序列。
    m = ⌊ t n 2 ⌋ m=\lfloor \frac{t}{n2}\rfloor m=⌊n2t​⌋.

    这是因为满足单调性：当复制t次是子序列，那么当小于t次，显然也是子序列。
    当复制t+1次已经不是子序列，那么大于t+1时，同样不再是子序列。（因为有多余的在s1*n1无法找到）

    在这里，首先认为s1*INF是无限多的。由于具有周期性，可以使用0—size-1的位置表示。
    f[i][j].指从第i个位置开始，得到 2 j 2^j 2j个重复的s2的子序列所需要的最短的长度。

    值得一提的是要注意有无解的情况

    #include 
using namespace std;
char s1[120], s2[120];
int n1, n2;
typedef long long ll;
#define M 31
ll f[120][M];
int main()
{
    while(scanf("%s%d%s%d", s2, &n2, s1, &n1) != EOF)//由于具有取模操作，所以两个字符串从0开始计算
    {
        //暴力枚举f[i][0]
        bool fault = false;//无解情况
        int len1 = strlen(s1), len2 = strlen(s2);
        for(int i = 0; i < len1; i++)
        {
            f[i][0] = 0;
            int p = i;//在s1中的位置指针
            for(int j = 0; j < len2; j++)
            {
                int cnt = 0;
                while(s1[p] != s2[j])
                {
                    p = (p+1)%len1;
                    cnt++;
                    if(cnt >= len1) {fault = true; break;}
                }
                if(fault) break;
                f[i][0] += 1+cnt;
                p = (p+1)%len1;
            }
            if(fault) break;
        }
        if(fault){
            puts("0");
            continue;
        }
        //for(int i = 0; i < len1; i++) printf("%d\t", f[i][0]);

        //初始化倍增DP
        for(int j = 1; j < M; j++)
        {
            for(int i = 0; i < len1; i++)
            {
                f[i][j] = f[i][j-1] + f[ (i+f[i][j-1])%len1 ][j-1];
            }
        }
        ll ans = 0;
        //进行拼凑
        for(int i = 0; i < len1; i++)
        {
            ll t = 0, p = i;
            for(int j = M-1; j >= 0; j--)
            {
                if(p + f[p%len1][j] > len1*n1) continue;
                p += f[p%len1][j];
                t += 1 << j;
            }
            ans = max(ans, t);
        }
        printf("%d", ans/n2);
    }
    return 0;
}
/*
格外注意：我的f[][]数组的第一位的取值范围仅仅可以是0~len-1
*/

    • 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
  • 相关阅读:
    机器学习复习（待更新）
    AUSBC3.0, 震撼来袭！(UVC Camera)
    过滤器 监听器
    Apache IoTDB 分布式架构三部曲（二）分片与负载均衡
    【数据科学项目1】：构建你的第一个数据科学项目
    Linux开发——GCC编译器（八）
    数据挖掘（3）特征化
    LSTM -长短期记忆网络(RNN循环神经网络)
    Android -- 每日一问：怎么理解 Activity 的生命周期？
    通讯协议学习之路：RS422协议理论
  • 原文地址：https://blog.csdn.net/xjsc01/article/details/126068270