最长子序列问题的动态规划解法
动态规划是解决子序列问题的有效方法，以下是几种常见子序列问题的解决方案。
最长递增子序列
给定一个数值序列，寻找最长的递增子序列，元素不一定连续。
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N = 1001;
int main() {
int n;
scanf("%d", &n);
int maxLen = 1;
int dp[MAX_N];
int arr[MAX_N];
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (arr[j] < arr[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
maxLen = max(maxLen, dp[i]);
}
printf("%d\n", maxLen);
return 0;
}
修改比较条件可实现其他变体：
- 最长不降子序列：arr[j] ≤ arr[i]
- 最长递减子序列：arr[j] > arr[i]
- 最长不升子序列：arr[j] ≥ arr[i]
木棍加工问题
处理n个木棍，每个有长度和重量。机器设置时间取决于前后木棍的尺寸关系，求最小设置时间。
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_STICKS = 5001;
int main() {
int testCases;
scanf("%d", &testCases);
while (testCases--) {
int n;
scanf("%d", &n);
pair<int, int> sticks[MAX_STICKS];
for (int i = 0; i < n; i++) {
scanf("%d%d", &sticks[i].first, &sticks[i].second);
}
sort(sticks, sticks + n);
int count = 0;
int seq[MAX_STICKS];
for (int i = 0; i < n; i++) {
int left = -1;
int right = count;
while (right - left > 1) {
int mid = (left + right) / 2;
if (seq[mid] > sticks[i].second) {
left = mid;
} else {
right = mid;
}
}
seq[right] = sticks[i].second;
if (right == count) {
count++;
}
}
printf("%d\n", count);
}
return 0;
}
士兵队列问题
调整士兵队列，使得每个士兵至少能看到一侧的尽头，求最少需要移除的士兵数。
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_SOLDIERS = 1005;
int main() {
double heights[MAX_SOLDIERS];
int n;
scanf("%d", &n);
int leftDP[MAX_SOLDIERS], rightDP[MAX_SOLDIERS];
for (int i = 0; i < n; i++) {
scanf("%lf", &heights[i]);
leftDP[i] = 1;
for (int j = 0; j < i; j++) {
if (heights[j] < heights[i]) {
leftDP[i] = max(leftDP[i], leftDP[j] + 1);
}
}
}
for (int i = n - 1; i >= 0; i--) {
rightDP[i] = 1;
for (int j = n - 1; j > i; j--) {
if (heights[j] < heights[i]) {
rightDP[i] = max(rightDP[i], rightDP[j] + 1);
}
}
}
int maxRemain = 1;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
maxRemain = max(maxRemain, leftDP[i] + rightDP[j]);
}
}
printf("%d\n", n - maxRemain);
return 0;
}
最大子数组和
寻找数列中两个不重叠的连续子数组，使它们的和最大。
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_LEN = 50005;
const int MIN_VAL = -10000;
int main() {
int tests;
scanf("%d", &tests);
while (tests--) {
int n;
scanf("%d", &n);
int leftMax[MAX_LEN], rightMax[MAX_LEN];
leftMax[0] = rightMax[n + 1] = MIN_VAL;
int arr[MAX_LEN];
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
leftMax[i + 1] = max(arr[i], leftMax[i] + arr[i]);
}
for (int i = 1; i <= n; i++) {
leftMax[i] = max(leftMax[i - 1], leftMax[i]);
}
for (int i = n; i > 0; i--) {
rightMax[i] = max(arr[i - 1], rightMax[i + 1] + arr[i - 1]);
}
for (int i = n; i > 0; i--) {
rightMax[i] = max(rightMax[i + 1], rightMax[i]);
}
int result = MIN_VAL;
for (int i = 1; i < n; i++) {
result = max(result, leftMax[i] + rightMax[i + 1]);
}
printf("%d\n", result);
}
return 0;
}
最大子矩阵和
在二维矩阵中寻找元素和最大的子矩阵。
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
int bestSum = -128;
int matrix[101][101] = {0};
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int value;
scanf("%d", &value);
matrix[i][j] = matrix[i][j - 1] + value;
}
}
for (int endCol = 1; endCol <= n; endCol++) {
for (int startCol = 0; startCol < endCol; startCol++) {
for (int row = 1, currentSum = 0; row <= n; row++) {
int colSum = matrix[row][endCol] - matrix[row][startCol];
currentSum = colSum + max(0, currentSum);
bestSum = max(bestSum, currentSum);
}
}
}
printf("%d\n", bestSum);
return 0;
}
