动态规划2

也是学到新算法了——卡丹算法，用于求解“最大子段和”问题

我们从左往右扫描数组，用一个变量维护以当前下标i为结尾的子段最大和。再不断更新一个全局最大值。

#include <iostream>
using namespace std;#define MAX_N 1001
int a[MAX_N];
int n;int main() {cin >> n ;for (int i = 1; i <= n; i++) {cin >> a[i];}int maxSum = a[0]; // 当前最大子段和int current = a[0]; // 当前以i结尾的子段和for (int i = 1; i < n; i++) {current = max(a[i], current + a[i]);maxSum = max(maxSum, current); // 更新全局最大值}cout << maxSum << endl;return 0;
}

LCS，有点难

个人理解就是，dp[i][j]，就是要去讨论s1的第i个字符和s2的第j个字符能否匹配上的问题。如果能匹配上，皆大欢喜，这就是dp[i][j]的终点。如果匹配不上，说明ij“不能同时纳入’，必须舍弃一个，那就有两种情况，舍弃i或者舍弃j。然后再去讨论前面的情况。（实际上我们从小到大迭代，前面的最优解已经书写好了）

// 定义DP数组
int dp[MAXLEN + 1][MAXLEN + 1];for (int i = 0; i <= m; i++) {for (int j = 0; j <= n; j++) {if (i == 0 || j == 0)dp[i][j] = 0;else if (s1[i - 1] == s2[j - 1])dp[i][j] = dp[i - 1][j - 1] + 1;elsedp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);}
}
return dp[m][n];

优先队列

这个代码需要你好好品味！

#include <iostream>
#include <queue>
#include <vector>
#include <tuple>
#include <algorithm>
#include <cstring>
using namespace std;const int INF = 1e9;
int N, K, A, B, C;
int grid[105][105];
int dp[105][105][15]; // dp[x][y][fuel]int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} }; // 上下左右struct Node {int x, y, fuel, cost;bool operator<(const Node& other) const {return cost > other.cost;}
};bool inGrid(int x, int y) {return x >= 1 && x <= N && y >= 1 && y <= N;
}int main() {cin >> N >> K >> A >> B >> C;for (int i = 1; i <= N; i++) {for (int j = 1; j <= N; j++) {cin >> grid[i][j];}}// 初始化for (int i = 0; i <= N; i++) {for (int j = 0; j <= N; j++) {for (int k = 0; k <= K; k++)dp[i][j][k] = INF;}}priority_queue<Node> pq;dp[1][1][K] = 0;pq.push({ 1, 1, K, 0 });while (!pq.empty()) {Node cur = pq.top();pq.pop();int x = cur.x, y = cur.y, fuel = cur.fuel, cost = cur.cost;if (dp[x][y][fuel] < cost) continue;// 已有更优解if (fuel == 0) {if (grid[x][y] == 1) {if (dp[x][y][K] > cost + A) {dp[x][y][K] = cost + A;pq.push({ x, y, K, cost + A });}}else {// 当前不是油库，可以建一个再加油if (dp[x][y][K] > cost + A + C) {dp[x][y][K] = cost + A + C;pq.push({ x, y, K, cost + A + C });}}continue; // 原地操作完了，再开始下轮跳出，因为当前这个fuel0的状态是无法继续的！你加满油之后就是另外的状态了！}for (int d = 0; d < 4; d++) {int nx = x + dir[d][0];int ny = y + dir[d][1];if (!inGrid(nx, ny)) continue; // 超出边界int nFuel = fuel - 1;int nCost = cost;if ((nx < x) || (ny < y)) {nCost += B;}if (grid[nx][ny] == 1) { // 有油库，加油if (dp[nx][ny][K] > nCost + A) {dp[nx][ny][K] = nCost + A;pq.push({ nx, ny, K, nCost + A });}}else { // 不加油if (dp[nx][ny][nFuel] > nCost) {dp[nx][ny][nFuel] = nCost;pq.push({ nx, ny, nFuel, nCost });}// 建立新油库if (dp[nx][ny][K] > nCost + A + C) {dp[nx][ny][K] = nCost + A + C;pq.push({ nx, ny, K, nCost + A + C });}}}}int ans = INF;for (int i = 0; i <= K; i++) {ans = min(ans, dp[N][N][i]);}cout << ans << endl;return 0;
}