首页 > 其他分享 >洛谷题单指南-动态规划1-P3842 [TJOI2007] 线段

洛谷题单指南-动态规划1-P3842 [TJOI2007] 线段

时间:2024-04-22 09:34:13浏览次数:34  
标签:P3842 路程 int 洛谷题 线段 abs 行右 端点 TJOI2007

原题链接: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

相关文章

  • 洛谷题单指南-动态规划1-P1077 [NOIP2012 普及组] 摆花
    原题链接:https://www.luogu.com.cn/problem/P1077题意解读:n种花选m个的选法,每种花数量为ai。解题思路:设dp[i][j]表示前i种花选j个的选法对于第i种花,可以选0,1,2...min(ai,j)个则有递推式:dp[i][j]=∑dp[i-1][j-k],k取0,1,2...min(ai,j)初始化dp[0][0]=1100分代码:#incl......
  • 洛谷题单指南-动态规划1-P1049 [NOIP2001 普及组] 装箱问题
    原题链接:https://www.luogu.com.cn/problem/P1049题意解读:装尽可能多的物品,使得总体积越大越好,即剩余空间最小,还是一个01背包问题,物品的体积就是其价值。解题思路:01背包模版题,物品体积、价值相同,直接采用一维dp。100分代码:#include<bits/stdc++.h>usingnamespacestd;co......
  • 洛谷题单指南-动态规划1-P1115 最大子段和
    原题链接:https://www.luogu.com.cn/problem/P1115题意解读:计算最大字段和,典型dp问题。解题思路:设a[]表示所有整数,f[i]表示以第i个数结束的最大字段和当f[i-1]>=0时,f[i]=f[i-1]+a[i]否则,f[i]=a[i]因此,递归式为f[i]=max(a[i],f[i-1]+a[i])注意整数可能为负,ans初始......
  • 洛谷题单指南-动态规划1-P1434 [SHOI2002] 滑雪
    原题链接:https://www.luogu.com.cn/problem/P1434题意解读:计算能滑行的最长距离。解题思路:设dp(i,j)表示从i,j可以滑行的最大距离对于4个方向i,j可以到达的点,ni,nj,如果可以滑过去(ni,ni所在点高度更低)则dp(i,j)=max(dp(i,j),1+dp(ni,nj))为了便于搜索4个方向的各条路径,......
  • 洛谷题单指南-动态规划1-P2196 [NOIP1996 提高组] 挖地雷
    原题链接:https://www.luogu.com.cn/problem/P2196题意解读:求一条路径,使得所有点地雷数之和最大。解题思路:1、DFS先建图,再从1~n点分别进行一次DFS,记录过程中地雷总数最大的,并且同时记录遍历的顺序。数据量不大,直接就可以过。100分代码:#include<bits/stdc++.h>usingnamespa......
  • 洛谷题单指南-动态规划1-P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles
    原题链接:https://www.luogu.com.cn/problem/P1216题意解读:计算数字三角形最高点到最后一行路径之和最大值,典型线性DP。解题思路:设a[i][j]表示数字三角形的值,设dp[i][j]表示从最高点到第i行第j列路径之和的最大值,由于每一步可以走到左下方的点也可以到达右下方的点,所以dp[i][......
  • 洛谷题单指南-数学基础问题-P1403 [AHOI2005] 约数研究
    原题链接:https://www.luogu.com.cn/problem/P1403题意解读:计算1~n每个数的约数个数之和。解题思路:1、数学方法1~n的约数范围也在1~n,要计算每个数的约数个数之和可以从约数出发,比如约数是x,那么在1~n中一共有n/x个数包含x这个约数x从1一直枚举到n,就可以得出每个约数是多少个......
  • 洛谷题单指南-数学基础问题-P3601 签到题
    原题链接:https://www.luogu.com.cn/problem/P3601题意解读:求l~r范围内所有qiandao(x)之和,qiandao(x)为小于等于x的数中,与x不互质的数的个数。注意取模。解题思路:欧拉函数定义:phi(x)=x*(1-1/p1)*(1-1/p2)*...*(1-1/pn),p1,p2...pn为x的所有质因子其中:phi(x)表示1~x中所......
  • 洛谷题单指南-数学基础问题-P2660 zzc 种田
    原题链接:https://www.luogu.com.cn/problem/P2660题意解读:对一个长方形,切割出最少数量的正方形,计算所有正方形的边长。解题思路:长方形长、宽为x,y先判断x,y哪个长,哪个短长的作为l,短的作为s先切出s*s的正方形,一共可以切出l/s个,累加周长ans+=l/s*s*4在对剩下的s*......
  • 洛谷题单指南-数学基础问题-P2651 添加括号III
    原题链接:https://www.luogu.com.cn/problem/P2651题意解读:计算能否在除法a1​/a2​/a3​/.../an​式子中加括号,将一部分数变成分子,使得除法结果是整数。解题思路:在a1​/a2​/a3​/.../an​中,无论怎么加括号,a1一定是分子,a2一定是分母,那么可以判断把a3...an都作为分子,是否能除尽......