区间DP Zoj 3537 Cake 区间DP 最优三角形剖分

下面是别人的解题报告的链接，讲解很详细，要注意细节的处理。。。以及为什么可以这样做

http://blog.csdn.net/woshi250hua/article/details/7824433

我的代码：

 //其中求凸包用的是Andrew扫描算法，复杂度主要为排序O(n*logn)，扫描为O(n)

 #include <cstdio>

 #include <algorithm>

 #define INF 100000000

 #define min(a,b) a<b?a:b;

 using namespace std;

 //点的定义

 struct point

 {

     int x,y;

     bool  operator <(const point & other) const

     {

         if(x == other.x)   return y < other.y;

         return x < other.x;

     };

 } convex[];

 //判断是往左还是往右

 bool checkDir(point p0,point p1,point p2)

 {

     //往左返回true

     if((p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y) * (p2.x-p0.x) <= )

         return true;

     else return false;

 }

 //求凸包的算法···，返回凸包的顶点数,输入的顶点数>=3。0,1,2特判，如果有需要的话

 int andrew(point p[],int n)

 {

     sort(p,p+n);

     int m=;

     for(int i=; i<n; ++i)

     {

         while(m >  && checkDir(convex[m-],convex[m-],p[i]) ) --m;

         convex[m++] = p[i];

     }

     int k =m;

     for(int i=n-; i>=; --i)

     {

         while(m > k && checkDir(convex[m-],convex[m-],p[i]) ) --m;

         convex[m++] = p[i];

     }

     return m-;

 }

 int main()

 {

 //    freopen("in.cpp","r",stdin);

     int n,m,dp[][],cost[][];

     struct point p[];

     while(scanf("%d%d",&n,&m) != EOF)

     {

         //读入数据

         for(int i=; i<n; ++i)

             scanf("%d%d",&p[i].x,&p[i].y);

         int num = andrew(p,n);

         if(num != n)

         {

             printf("I can't cut.\n");

             continue;

         }

         //预处理dp数组的值

         for(int i=; i<n; ++i)

         {

             for(int j=; j<n; ++j)

                 dp[i][j] = INF;

             dp[i][(i+)%n] = ;

         }

         //预处理cost数组的值

         for(int i=; i<n; ++i)

         {

             cost[i][i+] = cost[i+][i] = ;

             cost[i][i] =;

         }

         for(int i=; i<n; ++i)

             for(int j=i+; j<n; ++j)

                 cost[j][i] = cost[i][j] = abs(convex[i].x + convex[j].x) * abs(convex[i].y+convex[j].y)%m;

         //DP

         for(int i=n-; i>=; --i)

             for(int j=i+; j<n; ++j)

                 for(int k=i+; k < j; ++k)

                     dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]+cost[k][i]+cost[k][j]);

         printf("%d\n",dp[][n-]);

     }

     return ;

 }