HDU_3480

    首先，一个贪心的思路就是如果将元素排个序，选择的一定是连续的区间，因为如果选了两个值，那么这个区间就可以选两个值之间的任何一个值，这样是不会改变这个区间的cost的。

    如果用w[i][j]表示(a[j]-a[i])*(a[j]-a[i])，写出状态转移方程后会得到f[i][j]=min{f[i-1][k-1]+w[k,j]}，这个和POJ_1160的状态转移方程是一样的，如果我们能够证明w为凸，那么这个题就可以用四边形不等式优化。

    由于w[i+1][j]-w[i][j]=(a[i]-a[i+1])*(2*a[j]-a[i+1]-a[i])，这个表达式是随着j的增加单调递减的，所以就有w[i+1][j+1]-w[i][j+1]<=w[i+1][j]-w[i][j]，也就是w[i][j]+w[i+1][j+1]<=w[i][j+1]+w[i+1][j]，所以w是凸的，进而我们就可以放心地使用四边形不等式优化dp了。

    其实，如果我们把状态转移方程写成f[i][j]=min{f[i-1][k-1]+ (a[j]-a[k])*(a[j]-a[k])}的话，不妨假设k的取值x、y满足x<y，且y要比x优，这时就能化简成a[j]>(a[y]*a[y]-a[x]*a[x]+f[i-1][y-1]-f[i-1][x-1])/(2*a[y]-2*a[x])，这样就又变成能够使用斜率优化了，而且用斜率优化比较好用滚动数组实现，能节省不少空间。

//四边形不等式优化dp #include
     
       #include
      
        #include
       
         #define MAXD 10010 #define INF 0x3f3f3f3f int N, M, a[MAXD], f[MAXD][MAXD], K[MAXD][MAXD]; int cmp(const void *_p, const void *_q) {
   int *p = (int *)_p, *q = (int *)_q; return *p - *q; } int getw(int x, int y) {
   return (a[y] - a[x]) * (a[y] - a[x]); } void init() {
   int i, j, k;     scanf("%d%d", &N, &M); for(i = 1; i <= N; i ++)         scanf("%d", &a[i]); } void solve() {
   int i, j, k, p, t;     qsort(a + 1, N, sizeof(a[0]), cmp); for(i = 0; i <= N; i ++)     {
           f[i][i] = 0;         K[i][i] = i;     } for(i = M + 2; i <= N; i ++)         K[M + 1][i] = i; for(p = 1; p <= N - M; p ++)     {
           f[0][p] = INF; for(i = 1; i <= M; i ++)         {
               j = i + p;             f[i][j] = INF; for(k = K[i][j - 1]; k <= K[i + 1][j]; k ++)             {
                   t = f[i - 1][k - 1] + getw(k, j); if(t < f[i][j])                 {
                       f[i][j] = t;                     K[i][j] = k;                 }             }         }     }     printf("%d\n", f[M][N]); } int main() {
   int t, tt;     scanf("%d", &t); for(tt = 0; tt < t; tt ++)     {
           init();         printf("Case %d: ", tt + 1); if(M >= N)             printf("0\n"); else             solve();     } return 0; }
       
      
     

 

//斜率优化+单调队列 #include
     
       #include
      
        #include
       
         #define MAXD 10010 int N, M, a[MAXD], wa[MAXD], wb[MAXD], *f, *g, q[MAXD]; int cmp(const void *_p, const void *_q) {
   int *p = (int *)_p, *q = (int *)_q; return *p - *q; } void init() {
   int i, j, k;     scanf("%d%d", &N, &M); for(i = 1; i <= N; i ++)         scanf("%d", &a[i]); } int getw(int x, int y) {
   return (a[y] - a[x]) * (a[y] - a[x]); } int getf(int i) {
   return a[i] * a[i] + g[i - 1]; } void solve() {
   int i, j, k, front, rear, x, y, z, *t;     qsort(a + 1, N, sizeof(a[0]), cmp);     f = wa, g = wb; for(i = 1; i <= N; i ++)         g[i] = getw(1, i); for(i = 2; i <= M; i ++)     {
           front = rear = 0;         q[rear ++] = i; for(j = i; j <= N; j ++)         {
   while(front < rear - 1)             {
                   x = q[front], y = q[front + 1]; if(a[j] * 2 * (a[y] - a[x]) < getf(y) - getf(x)) break;                 ++ front;             }             x = q[front];             f[j] = g[x - 1] + getw(x, j); if(j < N)             {
                   q[rear] = j + 1; for(k = rear - 1; k > front; k --)                 {
                       x = q[k - 1], y = q[k], z = q[k + 1]; if((getf(y) - getf(x)) * (a[z] - a[y]) < (getf(z) - getf(y)) * (a[y] - a[x])) break;                     q[rear = k] = q[k + 1];                 }                 ++ rear;             }         }         t = f, f = g, g = t;     }     printf("%d\n", g[N]); } int main() {
   int t, tt;     scanf("%d", &t); for(tt = 0; tt < t; tt ++)     {
           init();         printf("Case %d: ", tt + 1); if(M >= N)             printf("0\n"); else             solve();     } return 0; }