• • 题目描述
    • • 输入格式
      • 输出格式
      • 数据范围
      • 输入样例：
      • 输出样例：
  • 动态规划：区间dp / 一维dp
    • 分析
    • 代码
    • 时间复杂度
  • 参考文章

题目传送门

题目描述

某条线路上有 NN 个火车站，按顺序依次编号为 1～N1～N。

对于第 ii 号车站（i≥2i≥2），11 号车站与该车站之间的距离为 aiai。

显然，aiai 序列是递增的。

乘客在购票时，有三种车票可选：

• 当起点站和终点站之间的距离 SS 满足 0
• 当起点站和终点站之间的距离 SS 满足 L1
• 当起点站和终点站之间的距离 SS 满足 L2

注意，由于只出售上述三种车票，所以当起点站和终点站之间的距离 SS 大于 L3L3 时，只能选择从中途一些车站下车，重新买票的方式不断延续旅途直至到达终点站。

换句话说，这种情况下，乘客至少要买两张或更多车票才能到达终点站。

保证任意两个相邻车站之间的距离不超过 L3L3。

现在，某乘客要在 AA 号车站上车，并在 BB 号车站下车。

请你计算他所需要的最小花费是多少。

输入格式

第一行包含 66 个整数 L1,L2,L3,C1,C2,C3L1,L2,L3,C1,C2,C3。

第二行包含两个整数 A,BA,B。

第三行包含一个整数 NN。

接下来 N?1N?1 行，每行包含一个整数，依次表示 a2～aNa2～aN，保证这 N?1N?1 个数严格单调递增。

输出格式

输出一个整数，表示乘客的最小花费。

数据范围

1≤L1 1≤C1 1≤A 1≤N≤10001≤N≤1000,
1≤ai≤1061≤ai≤106

输入样例：

1 2 3 1 2 3
1 2
2
2

输出样例：

2

动态规划：区间dp / 一维dp

分析

我想到的是区间dp，但是只过了八个点

在牛客清华机试题上有相同的题目，我把代码交上去过了

在牛客评论区看到一维dp的写法，记录一下

代码

区间dp代码

#include
#include
#include
using namespace std;
const int N = 1010;
const int INF = 0x3f3f3f3f;
int l1, l2, l3, c1, c2, c3;
int a, b;
int n;
int s[N];
LL f[N][N]; // f[i][j]表示从i到j的最小花费
  
// 要保证cost <= l3 
int get_fee(int cost)
{
	if   (cost <= l1) return c1;
	else if(cost <= l2)	   return c2;
	else if(cost <= l3)    return c3;
}  

int main()
{
	scanf("%d%d%d%d%d%d", &l1, &l2, &l3, &c1, &c2, &c3);
	
	scanf("%d%d", &a, &b);
	scanf("%d", &n);
	
	s[1] = 0;
	for(int i = 2; i <= n; i++)
	scanf("%d", &s[i]);
	
	int cost = s[b] - s[a];	
	
	if   (cost <= l1) printf("%d\n", c1);
	else if(cost <= l2)	   printf("%d\n", c2);
	else if(cost <= l3)    printf("%d\n", c3);
	else // 
	{
		// len = 1 
		for(int i = a + 1; i <= b; i++)
		{
			int cost = s[i] - s[i - 1]; // 一定小于l3 
			f[i-1][i] = get_fee(cost);
		}
		
		for(int len = 2; len <= b-a; len++)
		{
			for(int i = a; i + len <= b; i++)
			{
				int l = i, r = i + len;
				int cost = s[r] - s[l];
				if   (cost <= l1)      f[l][r] = c1;
				else if(cost <= l2)	   f[l][r] = c2;
				else if(cost <= l3)    f[l][r] = c3;
				else
				{
					f[l][r] = INF;
					
					for(int k = l+1; k <= r-1; k++) 
					{
						f[l][r] = min(f[l][r], f[l][k] + f[k][r]);
					}
				}
				
			}
		}
		printf("%lld\n", f[a][b]);
	}
	
	return 0;
		
} 

一维dp代码

#include 
#include 
#define N 500

int dist[N], cost[N];//第i个站的总里程、最少花费
int l1, l2, l3, c1, c2, c3;

int Price(int L)//L距离的票多少钱
{
    if(L<=l1) return c1;
    else if(L<=l2) return c2;
    else return c3;
}

int main()
{
    int n, from, to;
    while(scanf("%d%d%d%d%d%d",&l1,&l2,&l3,&c1,&c2,&c3)!=EOF)
    {
        dist[1]=0;//始发站里程为0
        scanf("%d %d", &from, &to);
        scanf("%d", &n);
        for(int i=2; i<=n; i++) scanf("%d", &dist[i]);
        cost[from]=0;//出发之前，没花一毛钱
        for(int i=from+1; i<=to; i++)//前进！！！
        {
            cost[i]=INT_MAX;//先假设到i站需要花无数的钱
            for(int j=from; j