CF704B Ant Man

考虑对于一个位置,如果它不是 $s,e$ ,那么这个位置必然有一个入度一个出度。也就是说一个位置的方案有从右边进入,从左边进入,向左边出去,向右边出去。

我们考虑当前已经填完了前 $i$ 个位置,到现在为止还剩 $j$ 个向左的边和 $k$ 个向右的边。不难发现,如果这个点不是 $s,e$ 的一种,那么对于任何一种填这个点边的方案,要么使向左的、向右的边的个数同时 $+1,-1$ 要么使向左、向右的边的个数不变,分别对应:

然后如果新增的点是 $s$ ,那么只能是

如果新增的点是 $t$ ,那么只能是反过来的。

于是我们考虑一个 $dp$ ,设 $dp[i][j]$ 表示当前在 $i$ 这个位置,然后:

  • 如果当前 $i < s,i < e$ ,那么还剩 $j$ 个向右,$j$ 个向左的边。
  • 如果当前 $s < i < e$ ,那么还剩 $j$ 个向右,$j - 1$ 个向左的边。
  • 如果当前 $e < i < s$,那么还剩 $j - 1$ 个向右,$j$ 个向左的边。
  • 如果当前 $i > s,i > e$ ,那么还剩 $j - 1$ 个向右,$j - 1$ 个向左的边。

考虑什么状态、转移不合法:

  • 如果 $j \le 0 , i \neq 0$ ,显然这个状态必然不合法。
  • 如果当前有 $i > s,i > e,i \neq n$ 那么对于 $j \le 1$ 都不合法。 因为如果这个位置在 $s,e$ 之后了,那么前面必须得有接口可以接入 $s-e$ 这条链。不然的话我们就会转移出 $s-t$ 一条链加上很多环的情况(不出意外应该会 WA 7)。
  • 如果当前有 $i > s,j = 1$ 不能走最前面说的第四种转移,虽然是从 $(i,j) \to (i,j)$ 但是这个位置前面并没有向左的边存在,所以不能这么接进去。
  • 同理的,如果当前有 $i > e,j = 1$ 不能走最前面说的第三种转移。(如果没有考虑后面两种情况不出意外会直接 WA 5)

代码写着还是蛮爽的,只是开始没考虑到特殊情况(好在特殊情况 $n=4$ 都能拍出来 QwQ)。

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 5006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , s , e;
ll dp[MAXN][MAXN];
int A[MAXN] , B[MAXN] , C[MAXN] , D[MAXN] , x[MAXN];

void solve() {
cin >> n >> s >> e;
rep( i , 1 , n ) scanf("%d",x + i);
rep( i , 1 , n ) scanf("%d",A + i);
rep( i , 1 , n ) scanf("%d",B + i);
rep( i , 1 , n ) scanf("%d",C + i);
rep( i , 1 , n ) scanf("%d",D + i);
memset( dp , 0x3f , sizeof dp );
dp[1][1] = ( s != 1 ? B[1] - x[1] : 0 ) + ( e != 1 ? D[1] - x[1] : 0 );
rep( i , 2 , n - 1 ) {
if( i != s && i != e ) {
rep( j , ( i > s && i > e ? 2 : 1 ) , i ) {
if( i <= s || j != 1 ) dp[i][j] = min( dp[i][j] , dp[i - 1][j] + B[i] + C[i] );
if( i <= e || j != 1 ) dp[i][j] = min( dp[i][j] , dp[i - 1][j] + A[i] + D[i] );
dp[i][j + 1] = min( dp[i][j + 1] , dp[i - 1][j] + B[i] - x[i] + D[i] - x[i] );
if( j != 1 ) dp[i][j - 1] = min( dp[i][j - 1] , dp[i - 1][j] + A[i] + x[i] + C[i] + x[i] );
}
} else if( i == s ) {
rep( j , 1 , i ) {
dp[i][j] = min( dp[i][j] , dp[i - 1][j] + C[i] + x[i] );
dp[i][j + 1] = min( dp[i][j + 1] , dp[i - 1][j] + D[i] - x[i] );
}
} else if( i == e ) {
rep( j , 1 , i ) {
dp[i][j + 1] = min( dp[i][j + 1] , dp[i - 1][j] + B[i] - x[i] );
dp[i][j] = min( dp[i][j] , dp[i - 1][j] + A[i] + x[i] );
}
}
}
// cout << dp[2][1] << endl;
// cout << dp[2][1] << endl;
ll res = 0;
// cout << dp[3][1] << endl;
// cout << C[n] + x[n] << endl;
res = dp[n - 1][1 + ( s != n && e != n )] + ( s != n ? A[n] + x[n] : 0 ) + ( e != n ? C[n] + x[n] : 0 );
cout << res << endl;
}

signed main() {
// freopen("input","r",stdin);
// int T;cin >> T;while( T-- ) solve();
solve();
}
文章作者: yijan
文章链接: https://yijan.co/2020/10/09/cf704b-ant-man/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog