xyq0220

未归档

题解(3)

/ 注册

全部文章 / 未归档（共9篇）

Codeforces 1155 D Beautiful Array DP，最大子段和

题意给出一个长度为\(n\)的数列和数字\(x\),经过最多一次操作将数列的一个子段的每个元素变为\(a[i]*x\),使该数列的最大子段和最大分析将这个数列分为3段考虑，第一段和第三段是未修改的，第二段是修改的子段设\(dp[i][j]\)为第\(i\)个数字为第\(j+1\)段的...

DP codeforces

2019-04-23

0 404

2019牛客暑期多校训练营（第二场）E 线段树维护dp转移矩阵

题意给一个\(n\times m\)的01矩阵，1代表有墙，否则没有，每一步可以从\(b[i][j]\)走到\(b[i+1][j]\),\(b[i][j-1]\),\(b[i][j+1]\)，有两种询问： \(q=1\),将\(b[x][y]\)的状态反转 \(q=2\),计算从\(...

线段树 DP 矩阵

2019-08-16

0 401

2019牛客暑期多校训练营（第一场）I dp+线段树

题意给出n个点，每个点有a，b两个属性，让你从左下角到右上角划一条线，线的左边每个点的贡献是\(a_i\)，线的右边每个点的贡献是\(b_i\)，使得两部分的总和最大。分析找一条折线将点分割开，使总和最大。把y离散化，然后点按x排序，设\(dp[i]\)为经过第\(i\)个点(该...

DP 线段树

2019-08-20

0 404

洛谷P3193 GT考试 kmp+矩阵优化dp

题意求\(N\)位数字序列（可以有前导0）中不出现某\(M\)位子串的个数，模\(K\)。 \(N<=10^9,M<=20,K<=1000\) 分析设\(dp[i][j]\)表示匹配串下标\(i\)匹配到模式串下标\(j\)时，满足要求的方案数；枚举匹配串的...

kmp 矩阵 DP

2019-09-03

0 476

codeforces 1272F dp+记录路径

题意给出两个括号序列 \(S\) 和 \(T\)，让你构造一个最短的合法括号序列使 \(S\) 和 \(T\) 是它的子序列。分析设 \(dp[i][j][k]\) 为这个最短的合法括号序列的前缀包含 \(S\) 的前 \(i\) 个字符，T的前 \(j\) 个字符且左括号的数量大于右括...

DP

2019-12-18

0 325

“科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛 C 张老师的旅行

题目链接分析设\(dp[l][r][0]\)为走过区间\([l,r]\)的景点且落脚点为\(l\)用的最短时间，\(dp[l][r][1]\)为走过区间\([l,r]\)的景点且落脚点为\(r\)用的最短时间。则有转移: \(dp[l][r][0]=min(dp[l+1][r][...

区间dp DP

2020-05-13

0 388

codeforces 1367 F1，F2 Flying Sort

题意给出一个长度为\(n\)的数组\(a\)，每次操作能将一个数移动到数组的首位或末尾，问最少经过多少次操作能将这个数组变成单调不降的。分析在\(F_1\)中数组\(a\)的每个数字互不相同，我们发现只要找到最长的连续上升子序列（连续指在数组排序后两个数字是相邻的），n减去它的长度\(l...

DP codeforces

2020-06-18

0 537

Gym-101810 G ACM International Collegiate Programming Contest, Amman Collegiate Programming Contest (2018)

题意字符串\(S\)的能量\(P(S)\)定义为 \[P(S)=\sum_{i=1}^{n}N_i\times V_i \] \(N_i\)是满足\(S_i=S_j\)的下标\(j(i<j\le n)\)的个数，\(V_i\)是字符\(S_i\)的\(ASCII\)码。给一...

贪心 DP

2020-07-11

0 424

Codeforces 1155 D Beautiful Array DP，最大子段和

题意给出一个长度为\(n\)的数列和数字\(x\),经过最多一次操作将数列的一个子段的每个元素变为\(a[i]*x\),使该数列的最大子段和最大分析将这个数列分为3段考虑，第一段和第三段是未修改的，第二段是修改的子段设\(dp[i][j]\)为第\(i\)个数字为第\(j+1\)段的...

DP codeforces

2019-04-23

0 548