原题链接:https://www.luogu.com.cn/problem/P3842
题意解读:计算1-n的最短路,且每行要覆盖线段。
解题思路:
既然要每行覆盖线段,那往下一行走时,必然是从线段的端点往下,有可能是从左端点往下,也有可能是从右端点往下。
当已知第i行,从1走到第i行的左端点且要覆盖第i行线段的路程可以计算,从1走到第i行右端点且要覆盖第i行线段的路程也可以计算,
所以每走到一行的左、右端点的最短路程可以通过递推形式解决,而两种状态可以用两个数组定义递推式。
设l[],r[]表示每行的左、右端点
设f[i]表示从1走到第i行左端点且覆盖了第i行线段的最短路程, g[i]表示从1走到第i行右端点且覆盖了第i行线段的最短路程
1、f[i]可以从第i-1行左端点走过来
f[i] = f[i-1] + abs(l[i-1]-r[i]) + r[i] - l[i] + 1
说明:
走到i-1左端点的最短路程f[i-1];
先从第i-1行左端点,往下一步走到第i行,此时位置在l[i-1],路程+1;
由于要覆盖第i行的线段,先从第i行l[i-1]走到第i行右端点r[i],路程abs(l[i-1]-r[i]);
再从第i行右端点走到第i行左端点,路程r[i] - l[i];
全部加起来,即得f[i] = f[i-1] + abs(l[i-1]-r[i]) + r[i] - l[i] + 1。
2、f[i]可以从第i-1行走端点走过来
f[i] = g[i-1] + abs(r[i-1]-r[i]) + r[i] - l[i] + 1
分析过程同上,略。
所以:f[i] =min(f[i-1] +abs(l[i-1]-r[i]) +r[i] -l[i] +1, g[i-1] +abs(r[i-1]-r[i]) +r[i] -l[i] +1)。
同理:
3、g[i]可以从第i-1行左端点走过来 g[i] = f[i-1] +abs(l[i-1]-l[i]) +r[i] -l[i] +1 4、g[i]可以从第i-1行右端点走过来 g[i] = g[i-1] +abs(r[i-1]-l[i]) +r[i] -l[i] +1 所以:g[i] = min(f[i-1] +abs(l[i-1]-l[i]) +r[i] -l[i] +1, g[i-1] +abs(r[i-1]-l[i]) +r[i] -l[i] +1)。 初始值: 从1走到第1行左端点且覆盖第1行线段的最短路程:f[1] =r[1] -1+r[1] -l[1] 从1走到第1行右端点且覆盖第1行线段的最短路程:g[1] =r[1] -1 100分代码:#include <bits/stdc++.h>
using namespace std;
const int N = 20005;
int n;
int l[N], r[N]; //l:左端点,r:右端点
int f[N], g[N]; //f[i]:从1走到第i行左端点且覆盖第i行线段的最短路程,g[i]:从1走到第i行右端点且覆盖第i行线段的最短路程
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> l[i] >> r[i];
f[1] = r[1] - 1 + r[1] - l[1];
g[1] = r[1] - 1;
for(int i = 2; i <= n; i++)
{
f[i] = min(f[i-1] + abs(l[i-1]-r[i]) + r[i] - l[i] + 1, g[i-1] + abs(r[i-1]-r[i]) + r[i] - l[i] + 1);
g[i] = min(f[i-1] + abs(l[i-1]-l[i]) + r[i] - l[i] + 1, g[i-1] + abs(r[i-1]-l[i]) + r[i] - l[i] + 1);
}
cout << min(f[n] + n - l[n], g[n] + n - r[n]);
return 0;
}
标签:P3842,路程,int,洛谷题,线段,abs,行右,端点,TJOI2007 From: https://www.cnblogs.com/jcwy/p/18150003