最短时间【题解】

最短时间【题解】

GHOJ的一道dp题

题目描述

OIer们今晚要去参观番禹夜间动物园，那里有一个远近闻名的俄罗斯马戏团，其票很难买到，一场最多只能有400个人观看演出，当然是一个人要一张票，而售票处规定，一个人每次最多只能买两张票。可是每个人去买票很是浪费时间，OIer们想，如果其中有n个人买票，如何才能节省时间呢？

假设第i同学买一张票需要时间ti（1≤i≤n），队伍中相邻的两位OIer（第j个人和第j+1个人）也可以由其中一位买两张票，而另一位就可以不用排队了，则这两位同学（第j个人和第j+1个人，1≤j≤n-1）买两张票的时间变为rj。假如rj小于t[j]+t[j+1]，则这样做就可以缩短后面的同学的等待时间，加快整个买票的过程。

现给出n，ti和rj的值，请编程求出使每个人都买到票的最短时间。

输入格式

共三行，

第一行是一个200以内的整数n（n≤200）；
第二行包含n个由至少一个空格分隔的0-100之间的整数ti（ti＜100）；
第三行包含n-1个由至少一个空格分隔的0-100之间的整数ri（ri＜100）。

输出格式

一行，为售票处售票的总时间。

输入样例

7
5 4 3 2 1 4 4
7 3 4 2 2 4

输出样例

14

解题思路

解法1

看到这道题，想必大家都能想到洛谷的P1880石子归并吧，其实两题都很类似，我们只要用石子归并的思想做这道题即可。

设 f[i][j] 表示从第 i 个人到第 j 个人排队买票的最短时间，则我们可以写出状态转移方程：

f[i][j] = min{ f[i][j],f[i][k - 1] + f[i][k + 2] + double_time[k] } (i <= k < j)

初始化：f[i][j] = time[i] + time[i + 1] + time[i + 2] + … + time[j]

解法1 AC代码

#include<iostream>
#include<algorithm>
using namespace std;
int tam[210],tm,s[210];
int n,f[210][210];