002

[FarmerLiuAng]

疫情期间, 由于各个城市的严重程度不同, 需要互相运输物资进行支援.

现有一条高速公路用来运送医疗物资, 这条高速公路上有 n 个城市, 编号分别为 1,2,⋯,n 有一定数量的运输车在城市之间运送物资, 每个城市都有一个加油站, 运输车可以在加油站进行油量补给(假设每次加油都把油箱加满), 但是每辆车最多补给 r 次.

假设以高速公路的一端为原点, 每个城市到原点的距离(沿着高速公路的距离)分别为 x1,x2,⋯,xn​, 一辆运输车油箱的容积为 V, 每公里消耗的油量为 c.(所有运输车油箱的规格均相同)

请问油箱的容积最小需要是多少才能保证每辆车都可以到达目的地.

Input

输入的第一行包含两个正整数 n∈[2,400],m∈[1,250000], 分别表示城市的数量以及运输车的数量.

第二行为 n 个正整数 x1,x2,⋯xn以升序排列, 分别表示高速公路上城市到原点的距离.

后续 m行, 每行包含 4 个整数 s∈[1,n],d∈[s+1,n],c∈[1,10^9],r∈[0,n], 分别表示运输车的起点, 终点, 每公里油耗以及允许油量补给的次数.

Output

输出在保证所有运输车可以到达目的地的情况下, 运输车油箱的最小容积

Sample Input 1

10 10 2 3 4 8 9 10 12 13 15 19 3 8 3 1 3 4 3 2 1 9 2 1 1 9 3 1 6 10 2 1 3 9 2 0 3 7 2 1 2 3 3 0 3 9 2 0 4 10 3 0

Sample Output 1

33

[dpbnnp]

![Uploading 图片.png…]()

[aoxf]

若有r次补给次数，但要途径n个城市 Condition1：n-2<=r 则油箱容积直接为距最远的两个相邻城市的所需汽油体积。

Condition2：n-2>r 则必有n-r-2次在经过城市时不能加油，那么，应使n个城市中的n-2段路径转变为r段路径，头尾城市不变，则每次找到相加后路径长度最短的相邻两条路，在这两段路的中间城市不加油，循环直至找出这n-r-2个不加油的城市，即找出这r个加油的城市，油箱容积则为最长相邻加油城市所需汽油体积。

每辆车的最小油箱容积tempv算出来后与当前最小油箱容积v比较，若tempv > v，则v = tempv。

[RonDen]

不会呀 :sob: :duck:

[aoxf]

include

include

int cityList[400] = {0}; int nodeList[400] = {0};

void deleteNode(int a, int b) { int c = a + 1; int length = nodeList[a + 1] + nodeList[a + 2]; for(int i = a + 1; i < b; i++) { if(nodeList[i] + nodeList[i + 1] < length) { length = nodeList[i] + nodeList[i + 1]; c = i; } }

//删除中间的node
nodeList[c] = nodeList[c] + nodeList[c + 1];
for(int i = c + 1; i < b; i++)
{
    nodeList[i] = nodeList[i + 1];
}

}

int findLongestNodeLength(int a, int b) { int length = nodeList[a]; for(int i = a; i <= b; i++) { if(nodeList[i] > length) { length = nodeList[i]; } } return length; }

int findLongestCityLength(int a, int b) { int length = cityList[a]; for(int i = a + 1; i < b; i++) { if(cityList[i] > length) { length = cityList[i]; } } return length; }

int main() { int n, m; int s; //start city int d; //end city int c; //gas consumption per km int r; //times int tempv = 0; int v = 0;

scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++)
{
    scanf("%d", &cityList[i]);
}
//使cityList数组中存储的是到前一个城市的距离
for(int i = n - 1; i > 0; i--)
{
    cityList[i] = cityList[i] - cityList[i - 1];
}
cityList[0] = 0;//第一个城市前没有城市

for (int i = 0; i < m; i++)
{
    scanf("%d", &s);
    scanf("%d", &d);
    scanf("%d", &c);
    scanf("%d", &r);
    if(d - s - 1 < r)
    {
        tempv = findLongestCityLength(s, d) * c;
    }
    else
    {
        // 先将对应的城市放置到nodeList中
        for(int k = 0; k < d - s + 1; k++)
        {
            nodeList[k] = cityList[s + k - 1];
        }
        nodeList[0] = 0;//第一个节点前没有节点
        // 开始合并node
        for(int j = 0; j < d - s - r - 1; j++)
        {
            deleteNode(0, d-s-j);
        }
        //找到最远的相邻node，使油箱容积为最远相邻node所需汽油体积
        tempv = findLongestNodeLength(0, r + 1) * c;
    }
    if(tempv > v)
    {
        v = tempv;
    }
}
return v;

}

[CAEsarer]

这个答案AC了吗，我提交wa了，哭。

[FarmerLiuAng]

这个不大行

[CAEsarer]

大家有没有搞到答案