http://community.topcoder.com/stat?c=problem_statement&pm=13485&rd=16078

很容易枚举，令(p,q)表示分别以其为结尾的相似的折线。则可以从p-1和q-1开始向前搜索判断这个子串是否符合题目要求。然后计算出折线的长度并统计出最大的即可。

主要难点在于理解什么样的两个串是相似的。并且找到一种能够不用除法的方式向前搜索以避免精度对其的影响。我的实现用了递归，其实没有必要。O(n^3)

vector
     
       d;            vector
      
        r;            bool   dpf[MAX_N+1][MAX_N+1];            double dp[MAX_N+1][MAX_N+1];            double Solve(int p,int q){                if (p==0 || q==0) return 0;                if(dpf[p][q]){ return dp[p][q];}                double res=0;                res=max(res,Solve(p-1,q));                res=max(res,Solve(p,q-1));                if (p==q) {                    dpf[p][q]=true;                    dp[p][q]=res;                    return res;                }                int l=0;                int fdd1,fdd2;                while(p-1-l>=0 && q-1-l>=0){                    if (l==1){                        fdd1=d[p-2]-d[p-1];                        fdd2=d[q-2]-d[q-1];                    }                    if(l>=1){                        int dd1=d[p-1-l]-d[p-l];                        int dd2=d[q-1-l]-d[q-l];                        int dr1=r[p-1-l]-r[p-l];                        int dr2=r[q-1-l]-r[q-l];                        if (dd1*fdd2!=dd2*fdd1) break;                        if (dr1*fdd2!=dr2*fdd1) break;                    }                    l++;                }                double len=0;                for(int i=1;i
       
        1){                    int aaa=1;                }                dpf[p][q]=true;                dp[p][q]=res;                return res;            }        double maxLength(vector 
        
          date, vector 
         
           rating)             {                 d=date;                r=rating;                n=d.size();                memset(dpf,false,sizeof(dpf));                return Solve(n,n);            }