【Luogu】动态规划三

P3842 [TJOI2007] 线段 - 洛谷

思路：

5道题里就这道算比较有意思的一道dp

按照贪心的想法，每一次我们都最好是走完后到端点处再往下走

所以我们这里定义 dp[i][0/1] 为走完第 i 行且位于 左/右端点

那么对于左端点，其可从上一个左边点走来，也可从右端点走来，所以转移方程很显然了

我们每次移动只需要加上 线段长 和 端点间的距离 即可

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define int long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
vector<pair<int, int>> lr(20005);
int dp[20005][2];
void solve()
{int n;cin >> n;for (int i = 1; i <= n; i++){cin >> lr[i].first >> lr[i].second;}dp[1][0] = lr[1].second + (lr[1].second - lr[1].first) - 1;dp[1][1] = lr[1].second - 1;for (int i = 2; i <= n; i++){int linelen = lr[i].second - lr[i].first + 1;dp[i][0] = min(dp[i - 1][0] + abs(lr[i - 1].first - lr[i].second) + linelen,dp[i - 1][1] + abs(lr[i - 1].second - lr[i].second) + linelen);dp[i][1] = min(dp[i - 1][0] + abs(lr[i - 1].first - lr[i].first) + linelen,dp[i - 1][1] + abs(lr[i - 1].second - lr[i].first) + linelen);}cout << min(dp[n][0] + n - lr[n].first, dp[n][1] + n - lr[n].second);
}
signed main()
{//cin.tie(0)->sync_with_stdio(false);int t = 1;//cin >> t;while (t--){solve();}return 0;
}