开学领书(book.cpp)

【题目描述】

新学期开始了，开学的第一件事就是领课本。小明和小红一起去，各领到了重为1的课本。

在学校的教学楼里，有N个楼梯口，他们要带着书从楼梯口1走到N。每个楼梯口有一个高度Hi。还有M座楼梯，每座楼梯连接楼梯口Si和Ti。为了维持秩序，所有的楼梯只能从编号小的楼梯口走向编号大的。

俗话说，“男女搭配，干活不累”，对他们也是如此。在回来的路上，小明和小红可以在一起走，也可以不在一起走。他们两人各有一个疲劳度。当两人在一起时，疲劳度增加他们对课本做功的P分之一（下取整）；不在一起时，疲劳度增加对课本做的功。他们提课本的力都是竖直向上的。

请你帮他们写一个程序，求出两人从1走到N，疲劳度之和的最小值。

【输入描述】

第1行，3个正整数N，M，P。

第2行，N个空格隔开的正整数Hi。

之后M行，每行两个正整数Si，Ti。

【输出描述】

一行，一个正整数表示两人从1走到N，疲劳度之和的最小值。

【样例输入】

4 4 2 1 5 3 4

1 2 2 3 3 4 4 2 【样例输出】

0 【数据范围】

对于20%数据，N<=10,M<=50.

对于30%数据，Hi单调上升。

对于全部数据，N<=1000,M<=10000。

这道题大概是DP，跪求大神给出方程，谢谢！！

如果实在写不出O(N^2)的算法，O(N^3)或O(N^4)的也行。