FJUT第四周寒假作业[JL]最后的晚餐(动态规划)

时间:2022-04-01 05:23:59

题目来源:http://210.34.193.66:8080/vj/Contest.jsp?cid=163#P4

[JL]最后的晚餐

TimeLimit:1000MS  MemoryLimit:1000KB
64-bit integer IO format:%lld
 
Problem Description

【题库搜索“JL”查看更多建兰题库题目】

话说YZJ编的某程序超时了1000倍(- -!),所以他不得不在自己家门口亲眼见证这个电影般的场景。虽然他不想错过这个美妙的时刻,但是他的肚子一再*,要求先吃完这最后的晚餐。

现在YZJ准备依次吃n道菜。但是他只使用勺子和筷子吃,勺子和筷子可以交替使用,但是同一种菜只能用一种餐具,在开饭前他拿的是筷子。用勺子和筷子吃第i道菜的时间分别是a_i和b_i。吃第i道菜之前筷子和勺子交换的时间为c_i。

现在请你告诉ABC按他的计划依次吃完这n道菜,最小需要多少时间。

Input

第一行,一个正整数n(1<=n<=100)

以下n行,分别是三个正整数a_i,b_i,c_i(1<=a_i,b_i,c_i<=30000)

数据范围及提示:

所有其他输入<=30000 N<=20

Output

一个数,最短时间

SampleInput

3

20 40 20

10 4 25

90 100 5

SampleOutput

139

题意很简单,dp的题找到初始状态和状态转移方程就分分钟A了。

进入DP的思维,试图用dp[i]表示第i道菜的最短时间。寻找初始状态,那么dp[0]肯定是要特殊求的。然后寻找状态转移方程。

但是从案例发现,dp[i]并不能表示状态,第一道菜不论是勺子还是筷子吃都是40min,那么就增加一维数组表示状态。最后用dp[][2]表示状态

dp[i][0]表示吃到第i道菜用勺子吃的最短总时间,dp[i][1]表示吃到第i道菜用筷子吃的最短总时间。

那么初始状态,dp[0][0]=a+c,dp[0][1]=b.

接下来吃每道菜的时间是上一状态下,四种选择后的最短时间(原来是勺子,换与不换两种;原来是筷子,换与不换两种)。于是状态转移方程。

FJUT第四周寒假作业[JL]最后的晚餐(动态规划)

FJUT第四周寒假作业[JL]最后的晚餐(动态规划)最后答案。