题目
https://codeforces.com/contest/1476/problem/C
思路
设$dp(i,j)$，$i$表示第$i$条链，$j$表示是否和第$i-1$条链连接，0表示不连接，1表示连接
考虑不连接的情况，对于第$i$条链，显然当前状态由第$i-1$条链的状态直接转移，即$dp(i,0)\leftarrow\max(dp(i-1,0),dp(i-1,1))$
考虑连接的情况，有三种转移方程：
当$a_i=b_i$时，只能从第$i$条链向左出发，到$i-1$返回，此时状态转移方程为$dp(i,1)\leftarrow c_i-1+2$
当$a_i\not=b_i$且$i-1=1$，此时与第一种情况一样，状态转移方程为$dp(i,1)\leftarrow dp(i-1,1)+2+c_i-1$
当$a_i\not=b_i$且$i-1\not=1$，此时的路径可能到$i-1$返回，也有可能到$i-2$、$i-3$返回等等，考虑到最优子结构，$i-2$、$i-3$以及后面的这些情况已经被最优选择，所以只需考虑$i-1$返回和非$i-1$返回的情况即可
此时的状态转移方程为$dp(i,1)\leftarrow\max(dp(i-1,1)-\vert a_i-b_i\vert+2+c_i-1,\vert a_i-b_i\vert+2+c_i-1)$
AC代码
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
| #include <bits/stdc++.h>
#define endl '\n'
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define lowbit(x) (x&-x)
using namespace std;
struct _IO { _IO() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); } }_io;
typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll, ll> pll;
const ll maxn = 1e5 + 5;;
ll a[maxn], b[maxn], c[maxn], dp[maxn][2];
int main()
{
ll T;
cin >> T;
while (T--)
{
ll n;
cin >> n;
for (ll i = 1; i <= n; ++i) cin >> c[i];
for (ll i = 1; i <= n; ++i) cin >> a[i];
for (ll i = 1; i <= n; ++i) cin >> b[i];
dp[1][1] = abs(a[2] - b[2]);
for (ll i = 2; i <= n; ++i)
{
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
if (a[i] == b[i])
{
dp[i][1] = c[i] - 1 + 2;
}
else
{
if (i - 1 == 1) dp[i][1] = dp[i - 1][1] + 2 + c[i] - 1;
else dp[i][1] = max(dp[i - 1][1] - abs(a[i] - b[i]) + 2 + c[i] - 1, abs(a[i] - b[i]) + 2 + c[i] - 1);
}
}
cout << max(dp[n][0], dp[n][1]) << endl;
}
return 0;
}
|