Trkly

分类

C++(8) CSS(3) HTML(11) Java(14) JavaScript(7) Python(2) 未归档(1) 杂项(1) 算法(7) 英语(3) 题解(28)

/ 注册

TA的专栏 6篇文章 0人订阅

算法竞赛进阶指南

6篇文章 1044人学习

全部文章（共3篇）

过河卒

这是一道比较简单的dp问题，根据题意进行模拟就可以了。有两个需要注意的点：转移方程为：dp[i][j]=dp[i-1][j]+dp[i][j-1]。棋盘起点为(0,0),为了防止数组越界，需要将棋盘起点转移至（1，1）。具体解决方法和思路在代码注释中都要详细讲解，希望大家可以...

DP

2020-07-13

0 539

最长公共子序列LCS

根据题目数据范围可以知道算法的时间复杂度应当是O(nlogn)。具体思路应当是将最长公共子序列问题转到最长上升子序列（LIS问题有时间复杂度O(nlogn)）。具体可以参考这篇文章：最长上升子序列例如：求上面两个序列的最长公共子序列，可以将上面的的序列 1 6 5 4 3 2 转换成 1 2...

DP

2020-07-13

0 672

最大子列和

题目描述给出一个长度为 n 的序列 a，选出其中连续且非空的一段使得这段和最大。输入格式第一行是一个整数，表示序列的长度 n。第二行有 n 个整数，第 i个整数表示序列的第 i个数字 \(a_i\) 。输出格式输出一行一个整数表示答案。输入输出样例输入 7 2 ...

分治 DP

2020-08-10

0 411