大内高手

题解

前端(1)

/ 注册

全部文章 / 题解（共7篇）

PAT1007 - Maximum Subsequence Sum

这是一道求最大连续子序列和的问题(DP问题)。除了求最大连续子序列的和之外，还需要输出最大连续子序列的起点和终点的值。 // runtime: 8ms // space: 424K // https://pintia.cn/problem-sets/994805342720868352/proble...

CPP DP PAT

2020-04-03

0 1157

0-1背包变形

代码和0-1背包非常之像，只是由原来的容量固定，求最大价值，最小邮票数是每个邮票的价值(权重)一样，都为1(枚)，在背包大小固定的情况，求最少的邮票数。 // runtime: 4ms // space: 496K #include <iostream> #include <alg...

CPP 背包问题 DP

2020-03-23

1 848

0-1背包问题

经典的0-1背包问题。代码中的backtracking部分是输出组成最大价值的编号。 // runtime: 4ms // space: 728K #include <iostream> #include <algorithm> #include <stack> ...

背包问题 DP

2020-03-18

0 820

最长公共子序列

状态转移方程为：当s1[i] = s2[j]时: 当s1[i] != s2[j]时: // runtime: 4ms // space: 504K // complexity: O(m*n) #include <iostream> #include <cstring&...

CPP DP

2020-03-18

5 775

合唱队形

两次DP求最长递增子序列，然后，结果是 // runtime: 3ms // space: 496K #include <iostream> #include <algorithm> using namespace std; const int MAX = 100; i...

CPP DP

2020-03-17

0 596

最大上升子序列和

最长递增子序列的变形问题。 // runtime: 4ms // space; 496K #include <iostream> #include <cstdio> using namespace std; const int MAX = 1000; int arr[MAX...

CPP DP

2020-03-17

3 837

最长递增(减)子序列

// runtime: 4ms // space: 504K #include <iostream> #include <cstdio> using namespace std; const int MAX = 25; int arr[MAX]; int dp[MAX]; ...

CPP DP

2020-03-17

3 821