求问： 最近经常遇到一些在环形中的dp题。这些题目会要求序号为1和n（即首尾）的点也要满足题目条件。那么如何对此进行无后效性的dp呢？请求dl帮助！！！！

下面是一道例题：

《花园改造》

时空限制：1S，512MB

【问题描述】

小X开始改造她的环形的花园了，具体来说她要在花园的环上种满n棵树。她现在有3种树：种子、小树苗和大树。每个位置上种不同的树会产生不同的满意度，具体来说在第i个位置，种种子会产生ai的满意度，种小树苗会产生bi的满意度，种大树会产生ci的满意度。为了获取最大的满意度之和，她只要在每个位置种上该位置满意度最大的树就行了。但是附近的巫婆告诉她，种子的边上（距离为1的相邻，下同）不能有种子，大树的边上不能有大树，小树苗的边上要么都是种子、要么都是大树，不然花园所有树不久就会枯死。小X当然不允许这种事情发生，所以她就向小Q求助了。可惜的是小Q也不知道应该怎么做，请聪明的你帮帮他吧。

注意哦，花园是环形的，也就是说第1个位置的边上不只是第2个位置，还有第n个位置；第n个位置的边上不只是第n−1个位置，还有第1个位置。

【输入格式】

第一行一个正整数n。

接下来n行，每行三个正整数ai,bi,ci，分别代表在第i个位置种种子、小树苗和大树的满意度。​

【输出格式】

一行，应当包含一个正整数，代表最大的满意度。

【输入样例】

4 12 35 22 33 12 22 35 13 26 37 15 22

【输出样例】

131

【样例说明】

分别种上满意度为35的小树苗、满意度为33的种子、满意度为26的大树、满意度为37的种子。

【数据范围】

对于20%的数据，满足3≤n≤20；

对于40%的数据，满足3≤n≤300；

对于60%的数据，满足3≤n≤1500；

对于所有数据，满足3≤n≤100000，且n为偶数，1≤ai,bi,ci≤10000

_ _

---

只要讲讲思路就可以了，再次感谢dl帮助！！！！！_ _