奶牛过山车问题题解

一、题目分析

题目要求在预算内设计出最大趣味值的过山车，关键条件：

1. 组件约束：每个组件有固定起始位置、长度、趣味值和成本；
2. 路径连续性：组件必须首尾相连，从位置0开始，到位置L结束；
3. 预算限制：总成本不超过B。

二、算法思路

1. 动态规划建模：

   • f[pos][cost]表示到达位置pos且花费成本为cost时的最大趣味值；
   • 状态转移需满足组件起始位置可达且成本不超过预算。

2. 状态转移：

   • 对每个组件，若其起始位置x可达且当前成本j加上组件成本不超过预算，更新终点x+w的状态；
   • 状态转移方程：f[x+w][j] = max(f[x][j-c]+f_val, f[x+w][j])。

3. 结果计算：

   • 遍历所有可能的成本，取位置L处的最大趣味值。

三、代码实现

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 1001
#define MOD 123
#define E 1e-6
using namespace std;

int l,n,b;
int f[N][N];  // f[pos][cost]表示到达位置pos且花费cost的最大趣味值
struct Node{
    int x;    // 起始位置
    int w;    // 长度
    int f;    // 趣味值
    int c;    // 成本
}cow[N*10];

// 按起始位置排序，相同则按长度排序
int cmp(Node a,Node b)
{
    if (a.x==b.x)
        return a.w<b.w;
    return a.x<b.x;
}

int main()
{
    scanf("%d%d%d",&l,&n,&b);
    for(int i=0;i<n;i++)
        scanf("%d%d%d%d",&cow[i].x,&cow[i].w,&cow[i].f,&cow[i].c);

    sort(cow,cow+n,cmp);  // 按起始位置排序

    memset(f,-1,sizeof(f));  // 初始化为不可达
    f[0][0]=0;  // 起点位置0，成本0，趣味值0

    // 遍历每个组件
    for(int i=0;i<n;i++)
        for(int j=cow[i].c;j<=b;j++)  // 遍历所有可能的成本
            if(f[cow[i].x][j-cow[i].c]!=-1)  // 起始位置可达
                // 更新终点状态
                f[cow[i].x+cow[i].w][j]=max(f[cow[i].x][j-cow[i].c]+cow[i].f,f[cow[i].x+cow[i].w][j]);

    // 计算结果：遍历所有可能的成本，取位置L的最大值
    int maxx=-1;
    for(int i=0;i<=b;i++)
        maxx=max(maxx,f[l][i]);

    printf("%d\n",maxx);

    return 0;
}

四、代码解释

1. 输入处理与排序：

   • 读取输入数据并按起始位置排序，确保后续处理有序。

2. DP数组初始化：

   • f数组初始化为-1，表示不可达；
   • f[0][0]=0表示起点位置0且成本为0时的趣味值为0。

3. 状态转移：

   • 对每个组件，遍历所有可能的成本j；
   • 若起始位置x可达且当前成本j能包含组件成本，则更新终点x+w的状态。

4. 结果计算：

   • 遍历所有可能的成本，取位置L处的最大趣味值；
   • 若最终结果仍为-1，表示无法到达位置L，输出-1。

五、示例解析

输入：

5 6 10  
0 2 20 6  
2 3 5 6  
0 1 2 1  
1 1 1 3  
1 2 5 4  
3 2 10 2  

1. 状态转移：

   • 组件3（0→1，成本1，趣味2）更新f[1][1]=2；
   • 组件5（1→3，成本4，趣味5）从f[1][1]转移，更新f[3][5]=7；
   • 组件6（3→5，成本2，趣味10）从f[3][5]转移，更新f[5][7]=17；
   • 其他可能路径因成本超限或无法连续被排除。

2. 结果：

   • 位置L=5的最大趣味值为17，总成本7≤10，符合预算。

六、复杂度分析

• 时间复杂度：O(N×B)，其中N为组件数，B为预算；
• 空间复杂度：O(L×B)，用于存储DP数组。

七、关键技巧

1. 动态规划：通过二维数组同时维护位置和成本状态；
2. 状态可达性判断：利用-1标记不可达状态，避免无效转移；
3. 排序优化：按起始位置排序确保处理顺序合理，避免遗漏可行路径。