poj3257（Cow Roller Coaster）DP - c++编程基础

题意：要连出一个从1-L的过山车线，给出n段可选的建设方案。每段都有起始位置，终止位置，代价，和乐趣程度。要实现1-L的长度中，相邻两端要首尾相连，总建设代价控制在B之内，问最多能获得多少乐趣程度。

解法：二维dp， num[i][j]记录恰好建设到i并且用掉代价j多能获得的最多乐趣。先将每段可选方案按照位置排序，然后进行转移。最后选max(num[L][i]),i from 0 to B;

代码：

/****************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              #include 
             
               using namespace std; #define eps 1e-8 typedef long long LL; struct point { int s,e,fun,cost; } points[10010]; bool operator<(point a,point b) { if(a.s!=b.s) return a.s
              
               b) continue; LL &tool=num[points[i].e][j+points[i].cost]; tool=max(tool,num[points[i].s-1][j]+points[i].fun); } } } LL ans=-1; for(int i=0;i<=b;i++) ans=max(ans,num[L][i]); cout<