首页 > 其他分享 >[CF762D] Maximum path 题解

[CF762D] Maximum path 题解

时间:2023-09-29 20:55:10浏览次数:39  
标签:遍历 int 题解 路径 回头 Maximum CF762D 列数 path

[CF762D] Maximum path 题解

想法

首先考虑问题的弱化版,如果不能往左走,能取到的最大值是多少。

这个问题可以用一个显然的 DP 解决,\(f_{i,j}\) 表示走到第 \(i\) 列,第 \(j\) 行,并且不会再访问这一列其它的方格,能取到的最大值。

转移可以从三个方向考虑,以 \(f_{i,1}\) 为例,黑色是当前状态,红黄蓝是可能的三个转移方向,每一个状态可以取到箭头经过的点的权值。\(f_{i,2}, f_{i,3}\) 同理。

思路

但是原题中人是可以往左回头走的,这样这个单纯的转移就不成立了,因为回头走会出现后效性。

既然如此,可以想一下有没有什么性质尚未被观察到。

根据人类的直觉,小人应该是不会回头走太多步的,这个直觉是正确的,小人最多回头走 \(1\) 格。

如图,黑色的路径和红色路径得到的权值是相等的。

猜测 所有的回头路径都有一个修正的路径对应

回头走的真谛是在遍历蓝色小人到黑色小人每一行的格子,如果能找到一条最多回头一次的路径也能遍历这些格子,就可以证明上面的引理。

观察到这种走法可以让要遍历的格子列数减去 2,而行位置不变。

那么如果要遍历的列数是奇数,可以直接一直走上图走法,剩余遍历列数是 1 时,直接往上走到目标点。

如果列数是偶数,则在剩余遍历列数是 2 时,走一次下图走法,回头一次走到目标点:

所以证明了对于任意一个最优解,都有一个最多只需要回头一次的路径得到的权值与其相等。

所以这样就好做了,我们只需要在弱化版的 DP 转移里面加上回头一次的情况。

\(f_{i, 2}\) 的转移不会出现回头的情况,而 \(f_{i,1}, f_{i, 3}\) 加上回头转移的即可,以 \(f_{i, 1}\) 为例,转移绿色路径:

问题得到了解决。

代码实现

时间复杂度:\(O(n)\)。

// Problem: Maximum path
// Author: Moyou
// Copyright (c) 2023 Moyou All rights reserved.
// Date: 2023-09-29 19:36:59

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
long long a[3][N], f[N][3];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 0; i < 3; i ++) {
        for(int j = 1; j <= n; j ++) {
            cin >> a[i][j];
        }
    }
    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;
    for(int i = 1; i <= n; i ++) {
        long long sum = 0;
        for(int j = 0; j < 3; j ++) {
            sum += a[j][i] + a[j][i - 1];
        }
        f[i][1] = max({f[i - 1][0] + a[0][i], f[i - 1][1], f[i - 1][2] + a[2][i]}) + a[1][i];
        f[i][0] = max({f[i - 1][0], f[i - 1][1] + a[1][i], f[i - 1][2] + a[2][i] + a[1][i]}) + a[0][i];
        f[i][2] = max({f[i - 1][2], f[i - 1][1] + a[1][i], f[i - 1][0] + a[0][i] + a[1][i]}) + a[2][i];
        if(i > 1) {
            f[i][0] = max(f[i][0], f[i - 2][2] + sum);
            f[i][2] = max(f[i][2], f[i - 2][0] + sum);
        }
    }
    cout << f[n][2] << '\n';
    return 0;
}

标签:遍历,int,题解,路径,回头,Maximum,CF762D,列数,path
From: https://www.cnblogs.com/MoyouSayuki/p/17737268.html

相关文章

  • 【日常收支账本】【Day03】通过ElementTree+XPath实现对XML文件的读写
    一、项目地址https://github.com/LinFeng-BingYi/DailyAccountBook二、新增1.解析xml文件1.1功能详述解析所设计的xml文件格式,并将所得数据存入变量。点击查看xml格式<DailyAccountBook><balance><fund><value>5000.00</value>......
  • P2216 [HAOI2007] 理想的正方形 题解
    Description给定\(n\timesm\)的矩阵,找大小为\(k\timesk\)的子矩阵\(a\),使得子矩阵\(\max\{a\}-\min\{a\}\)最小。SolutionSolution1枚举所有\(k\timesk\)的子矩阵,然后枚举最大值和最小值,时间复杂度\(O(n^4)\),期望得分\(20\)分。Solution2求最大值和最小......
  • CF1425F Flamingoes of Mystery 题解
    题目传送门前置知识前缀和&差分解法令\(sum_k=\sum\limits_{i=1}^{k}a_k\)。考虑分别输入\(sum_2\simsum_n\),故可以由于差分知识得到\(a_i=sum_i-sum_{i-1}(3\lei\len)\),接着输入\(a_2+a_3\)的值从而求出\(a_2=sum_3-a_3,a_1=sum_2-a_2\)。同时因为是交互题,记......
  • 【题解】[CQOI2008] 传感器网络
    题意给定一张有向无环图,从中选出一棵有根树(节点编号为\(0\simn\),树根为\(n\)),使得除根节点外所有节点的出度的最大值最小。除根节点外,依次输出每个节点的父亲,并要求字典序最小。(\(1\len\le50\))*注意:由于个人习惯,这里将节点编号重编为\(1\simn+1\),根节点即为\(n+1\)......
  • 雅思 outweigh 议论题解答方法
    Doyouthinktheadvantagesoutweighthedisadvantages?1.这是两面写作题2.必须分出多少/高低3.所以说这个题目基本等同于discuss的弱强写作结构,不要给自己增加负担觉得新学了一种题目。结构安排:1.引出争论/背景句+给出明确的偏向(…..doesmoregoodthan harm.)2.先......
  • ABC211D Number of Shortest paths
    分析一道显然的最短路,用dijkstra算法。计算最短路的同时,保存最短路个数,如果与当前最短路相同,最短路个数相加,否则到这个节点的最短路个数为上一个节点的最短路个数。AcceptedCode#include<bits/stdc++.h>usingnamespacestd;constintN=2e5+5;constintmod=1e9......
  • Broken robot 题解
    题目链接Rrokenrobot分析记\(f[i][j]\)为从\(i\)行\(j\)列到最后一行的期望,则\(f[i][j]=\begin{cases}\frac{1}{3}(f[i][j]+f[i][j+1]+f[i+1][j])+1&i=1\\\frac{1}{4}(f[i][j]+f[i][j-1]+f[i,j+1]+f[i+1][j])+1&1<i<m\\\frac{1}{3}(f[i][j]......
  • git clone项目报错fatal: fetch-pack: invalid index-pack output问题解决
    gitclone项目报错fatal:fetch-pack:invalidindex-packoutput问题解决原因出现该问题的原因是gitclone的项目过大导致项目拉去失败解决方法首先拉去项目最后一次提交gitclone--depth=1项目地址;拉取全部项目内容gitfetch--unshallow,一般不大的项目都可以......
  • ABC321题解
    以后应该都是从E开始。E:problemLCA题。我们枚举向上跳\(t\)步,跳到了\(y\)。假如说\(t=0\)那么我们计算\(\text{clac}(x,k)\)即可。(\(\text{clac}\)怎么算放在最后讲)否则计算\(\text{clac}(y,k)-\text{clac}(x>>(t-1),m-t-1)\)。(建议自己理解一下......
  • P2427 题解
    洛谷链接题目简述给定\(N\timesM\)的字符矩阵,有\(Q\)次询问,对于每次询问给出\(x,y\),求以\((x,y)\)为中心的最大正方形边长且正方形中字符均相同。思路看到数据范围较小,可以考虑深搜解决,约掉常数的时间复杂度最坏为\(O(q\times\min(n,m))\),勉强可以通过。(不过代码......