Znzryb's Blog
0%

CF-994-D. Shift + Esc （多变量优化dp）

Posted on Edited on

思路讲解

我们先考虑不向左循环移动的情况，那么实际上这个块要么从左边转移过来，要么从上边转移过来。

那么如果加了向左循环移动那？首先dp里存的东西变成了到达此块的总代价即题目中的（kx+y）（y即经过之点的权重之和）

转移的话，从上面转移还是简单，就是要多加一个 K* 向左循环移动次数就行。

如果需要从左边转移，那么要注意，此时只有第一个块需要加一个 K* 向左循环移动次数，后面的块是不需要的，这个要小心一点。

（其实严格来说只有第一行第一个块需要加，因为后面的块都是先从上面转移下来，已经加过一个这个了，不过我也懒得这么严格，因为我的左边界是无穷大除了第一行第一个块旁边是0）

AC代码

https://codeforces.com/contest/2049/submission/299989686

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>

typedef long long ll;
const ll MAXDP=1e15+7;
ll n,T,m,K;
ll maze[210][210];
ll dp[210][210][210],dpUp[210][210];
// dpUp是指无视向左循环移动次数的最优解

// move函数是以该位置为主体的，即移动
inline ll move(ll x, ll step){
    if(x+step<=m){
        return x+step;
    }else{
        return (x+step)%m;
    }
}
inline void init() {
    for(int i=0;i<=n;++i) {
        for(int j=0;j<=m;++j) {
            dpUp[i][j]=MAXDP;
            for(int k=0;k<=m;++k) {
                dp[i][j][k]=MAXDP;
            }
        }
    }
}


inline void solve(){
    std::cin>>n>>m>>K;
    // memset(maze,0,sizeof(maze));
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            std::cin>>maze[i][j];
        }
    }
    // memset(dp, 0x3f, sizeof(dp));
    // memset(dpUp, 0x3f, sizeof(dpUp));
    init();
    for(int i=0;i<m;++i) {  // 第1行左边的数我们全部设为0，否则没法推
        dp[1][0][i]=0;
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            for(int k=0;k<m;++k){ //k是循环移动次数，K时全局系数
                //    横向k要相等（向左循环移动次数要相等），纵向k不用相等
                if(j==1) {
                    dp[i][j][k]=std::min({dp[i][j][k],dpUp[i-1][j]+maze[i][move(j,k)]+k*K,
                        dp[i][j-1][k]+maze[i][move(j, k)]+K*k});
                }else {
                    dp[i][j][k]=std::min({dp[i][j][k],dpUp[i-1][j]+maze[i][move(j,k)]+k*K,
                        dp[i][j-1][k]+maze[i][move(j, k)]});
                }
            }
            for(int k=0;k<m;++k){
                dpUp[i][j]=std::min(dp[i][j][k],dpUp[i][j]);
            }
        }
    }
    std::cout<<dpUp[n][m]<<std::endl;
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);std::cout.tie(0);
    std::cin>>T;
    while (T--) {
        solve();
    }
    return 0;
}
/*
AC https://codeforces.com/contest/2049/submission/299989686
*/

心路历程（WA，TLE，MLE……）

这个转移公式不是每一次都要+kK，如果是从一个已经加过kK的地方转移过来的，那么就不用加了

1
2
3
4
5
6
7
8
9
10
11
12
for(int i=1;i<=n;++i){
    for(int j=1;j<=m;++j){
        for(int k=0;k<m;++k){ //k是循环移动次数，K时全局系数
            //    横向k要相等，纵向k不用相等
            dp[i][j][k]=std::min({dp[i][j][k],dpUp[i-1][j]+maze[i][move(j,k)]+k*K,
                dp[i][j-1][k]+maze[i][move(j, k)]+K*k});
        }
        for(int k=0;k<m;++k){
            dpUp[i][j]=std::min(dp[i][j][k],dpUp[i][j]);
        }
    }
}

https://codeforces.com/contest/2049/submission/299988064

TLE，因为memset()。

1
2
// memset(dp, 0x3f, sizeof(dp));
// memset(dpUp, 0x3f, sizeof(dpUp));