CF704B. Ant Man
Solution
经典
d
p
dp
dp，第一次见好像是在
Z
J
O
I
ZJOI
ZJOI的某题？ 先按
x
x
x排序 用
f
[
i
]
[
j
]
f[i][j]
f[i][j]表示放入前
i
i
i个数，有
j
j
j个端点（不算边界点）的最小代价。 每次可以： 1.合并两段折线 2.制造一段新的折线 3.延长一个线段 需要对于向上和向下分别考虑贡献，特判端点情况即可。
时间复杂度
O
(
n
2
)
O(n^2)
O(n2)。
Code
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <string.h>
#include <unordered_map>
#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define fi first
#define se second
using namespace std
;
template<typename T
>inline bool upmin(T
&x
,T y
) { return y
<x
?x
=y
,1:0; }
template<typename T
>inline bool upmax(T
&x
,T y
) { return x
<y
?x
=y
,1:0; }
typedef long long ll
;
typedef unsigned long long ull
;
typedef long double lod
;
typedef pair
<int,int> PR
;
typedef vector
<int> VI
;
const lod eps
=1e-11;
const lod pi
=acos(-1);
const int oo
=1<<30;
const ll loo
=1ll<<62;
const int mods
=998244353;
const int MAXN
=5005;
const int INF
=0x3f3f3f3f;
inline int read()
{
int f
=1,x
=0; char c
=getchar();
while (c
<'0'||c
>'9') { if (c
=='-') f
=-1; c
=getchar(); }
while (c
>='0'&&c
<='9') { x
=(x
<<3)+(x
<<1)+(c
^48); c
=getchar(); }
return x
*f
;
}
ll x
[MAXN
],a
[MAXN
],b
[MAXN
],c
[MAXN
],d
[MAXN
],f
[MAXN
][MAXN
];
signed main()
{
int n
=read(),S
=read(),T
=read();
for (int i
=1;i
<=n
;i
++) x
[i
]=read();
for (int i
=1;i
<=n
;i
++) a
[i
]=read();
for (int i
=1;i
<=n
;i
++) b
[i
]=read();
for (int i
=1;i
<=n
;i
++) c
[i
]=read();
for (int i
=1;i
<=n
;i
++) d
[i
]=read();
for (int i
=0;i
<=n
;i
++)
for (int j
=0;j
<=n
;j
++) f
[i
][j
]=loo
;
f
[0][0]=0;
for (int i
=1;i
<=n
;i
++)
for (int j
=(i
!=1);j
<n
;j
++)
{
if (i
==S
)
{
if (j
<n
) upmin(f
[i
][j
+1],f
[i
-1][j
]-x
[i
]+d
[i
]);
if (j
>0) upmin(f
[i
][j
-1],f
[i
-1][j
]+x
[i
]+c
[i
]);
}
else if (i
==T
)
{
if (j
<n
) upmin(f
[i
][j
+1],f
[i
-1][j
]-x
[i
]+b
[i
]);
if (j
>0) upmin(f
[i
][j
-1],f
[i
-1][j
]+x
[i
]+a
[i
]);
}
else
{
if (j
<n
-1) upmin(f
[i
][j
+2],f
[i
-1][j
]-x
[i
]*2+b
[i
]+d
[i
]);
if (j
>1) upmin(f
[i
][j
-2],f
[i
-1][j
]+x
[i
]*2+a
[i
]+c
[i
]);
if (j
>1||i
>T
) upmin(f
[i
][j
],f
[i
-1][j
]+b
[i
]+c
[i
]);
if (j
>1||i
>S
) upmin(f
[i
][j
],f
[i
-1][j
]+a
[i
]+d
[i
]);
}
}
printf("%lld\n",f
[n
][0]);
return 0;
}
