首页 > 其他分享 >P7365 [CTSC2002]颁奖典礼 题解

P7365 [CTSC2002]颁奖典礼 题解

时间:2022-11-04 21:01:46浏览次数:60  
标签:kg kf 题解 fi jf jg P7365 gi CTSC2002

一道神奇的有关网格的DP(一些大佬称其为暴力DP)。
这里将 “I” 字母分为的三个部分称为第一,二,三部分。

做法:设 fi,j,k,l(l∈[1,3]) 表示第 i 行,当前在第 l 部分,区间 [j,k]的最大面积。
由于第二部分必须比第一部分短一截,在暴力的时候就得在枚举第一部分的 j,k 时枚举第二部分的 j,k,pia的一下 n4 了。
于是出现了一个小技巧:使用另一个数组 gi,j,k,l(l∈[1,2]),
gi,jg,kg,1 记录 fi,jf,kf,1|jf∈[1,jg),kf∈(kg,m]的最大值,
gi,jg,kg,2 记录 fi,jf,kf,2|jf,kf∈(jg,kg)的最大值,
这样在不同部分的转移中就可以直接调用 g 数组而不用枚举 jg,kg 了。
最后我们会发现 i 这一维可以被轻松地压掉,但好像可以不压

标签:kg,kf,题解,fi,jf,jg,P7365,gi,CTSC2002
From: https://www.cnblogs.com/cotsheep/p/16859115.html

相关文章

  • 矩阵树定理学习笔记 & 洛谷 P4111 [HEOI2015]小 Z 的房间 题解
    矩阵树定理拉普拉斯矩阵无边权设无向图\(G\)有\(n\)个结点,则拉普拉斯矩阵\(L\)是一个\(n\timesn\)的矩阵,满足:\(L_{i,i}(i\inG)\)的值为结点\(i\)的度数......
  • 【题解】Luogu P8743 【[蓝桥杯 2021 省 A] 异或数列】
    最近刚好在刷博弈论,看到这道题没有题解,所以刚好来水一发题目链接[蓝桥杯2021省A]异或数列题目描述Alice和Bob正在玩一个异或数列的游戏。初始时,Alice和Bob......
  • Atcoder Beginner Contest ABC 275 Ex (H) Monster 题解
    先明确\(a_i\)是一个怪物的血量,\(b_i\)是攻击的代价。发现如果我们想攻击一个怪物,不如找出一个极大的包含它的区间,满足这个区间内所有怪物的攻击代价都不大于它本身的代价,......
  • 【题解】洛谷 P1134 [USACO3.2]阶乘问题
     1#include<iostream>2usingnamespacestd;34intmain(){5intn;6cin>>n;7intc=1,a=0,b=0;8for(inti=1;i......
  • LG4026 [SHOI2008]循环的债务 题解
    LG4026[SHOI2008]循环的债务给出三个整数\(x_1,x_2,x_3\)。\(x_1\)代表A欠B的钱数,\(x_2\)表示B欠C的钱数,\(x_3\)表示C欠A的钱数。接下来\(3\)行,每......
  • WiredTiger引擎编译 及 LT_PREREQ(2.2.6)问题解决
    近期需要为异构引擎做准备,wiredtiger以其优异的性能(B-tree和LSM-tree都支持)和稳定性(Mongodb的默认存储引擎)被我们备选为异构引擎里的一个子引擎,后续将深入wiredtiger......
  • CF 1749 题解
    比赛链接:https://codeforces.com/contest/1749题解:AB水题//bySkyRainWind#include<cstdio>#include<vector>#include<cstring>#include<iostream>#include......
  • P4774 倚天屠龙传 题解
    其实这道题的主体并不难,主要是细节很多我们可以把题目分成界限分明的两部分,第一部分,屠每条龙所用的剑只和当前拥有的剑有关。于是可以单独开一个数据结构按题目维护。另......
  • 2022 CSP-S题解
    T1:假期计划给定\(n\)个点\(m\)条边的无向图,每个点有一个点权。在图中选\(4\)个不同的点,从\(1\)号点出发完成\(5\)段行程:\(1\toA\toB\toC\toD\to1\),每......
  • JOIOI の塔 题解
    题目传送门洛谷上竟然还没有题解...题目分析简单贪心题。考虑倒过来寻找。显然,如果一个J想要配成一座塔,那么必须要找一个OI。O更简单,就是直接找到一个I放上去就......