复杂度不会算，大概比N多一点...


强烈建议不会的同学过两天再回头看（个人觉得思考太长时间也没意思。。。）


转移方程

dp[E]表示从S开始到E的最小票价(S为起点，E为终点）

dp[E]=min{dp[k]+C1,dp[k]+C2,dp[k]+C3}(k<E&&k>=S)

想了想还是不贴代码了，免得您像我一样，一不会就看DISCUSS。上了赛场可没DISCUSS看，呵呵。。。贴博客上吧
http://www.oeddyo.com/articles/poj-2355-railway-tickets-动态规划.html