[Codeforces1016C] Vasya And The Mushrooms (DP)

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：

链接：http://codeforces.com/contest/1016/problem/C

给出一个$2×n$的矩阵，一个人从$(1,1)$出发，每一个格子只能走一次，走完这$2n$个格子后使得带权和最大，问最大的带权和是多少。

容易发现走到最后一个格子之前路径可以分为两个部分：前半部分蛇皮走位，后半部分一个大回环。

但是决定走大回环的位置也是分奇偶的，于是我们预处理出每一行的前缀和$sa_i$和$sb_i$，以及两组后缀和，分别为拐弯前（$da_i、db_i$）和拐弯后（$ia_i、ib_i$）。

然后我们可以枚举拐弯的结点，并同时记录前面走蛇皮位的结果，同时讨论目前在下还是在上，决定大回环值。

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
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
const int maxn = 300003;
int dx[5] = {0, 0, 1, -1};
int dy[5] = {1, -1, 0, 0};
int n;
LL a[maxn], b[maxn];
LL sa[maxn], sb[maxn], ia[maxn], ib[maxn], da[maxn], db[maxn];

signed main() {
  // freopen("in", "r", stdin);
  while(~scanf("%d", &n)) {
    for(int i = 0; i < n; i++) scanf("%lld",&a[i]);
    for(int i = 0; i < n; i++) scanf("%lld",&b[i]);
    memset(sa, 0, sizeof(sa));
    memset(sb, 0, sizeof(sb));
    memset(ia, 0, sizeof(ia));
    memset(ib, 0, sizeof(ib));
    memset(da, 0, sizeof(da));
    memset(db, 0, sizeof(db));
    for(int i = n - 1; i >= 0; i--) {
      sa[i] = sa[i+1] + a[i];
      sb[i] = sb[i+1] + b[i];
      ia[i] = ia[i+1] + a[i] * (LL)(n-i-1LL);
      ib[i] = ib[i+1] + b[i] * (LL)(n-i-1LL);
      da[i] = da[i+1] + a[i] * (LL)i;
      db[i] = db[i+1] + b[i] * (LL)i;
    }
    LL ret = 0, tmp = 0;
    for(int i = 0; i < n; i++) {
      if(i & 1) {
        LL tr = db[i] + sb[i] * (2LL*i - i);
        tr += ia[i] + sa[i] * (2LL*i + n - i);
        ret = max(ret, tmp+tr);
        tmp += (2LL*i*b[i]);
        tmp += (2LL*i+1LL)*a[i];
      }
      else {
        LL tr = da[i] + sa[i] * (2LL*i - i);
        tr += ib[i] + sb[i] * (2LL*i + n - i);
        ret = max(ret, tmp+tr);
        tmp += (2LL*i*a[i]);
        tmp += (2LL*i+1LL)*b[i];
      }
    }
    printf("%lld\n", ret);
  }
  return 0;
}