postoffice.txt

这是一个关于post office的问题,代码不多,但是独到.

#include<stdio.h>
#define MaxV 301
#define MaxP 31
#define MaxC 1000000000
#define MinNum(a,b) (a>b?b:a)

int v,p;
long d[MaxV],min[MaxV][MaxP];

template<class T>
T abs(T a)
{if (a>0) return a; else return -a;}

void init()
{ int i,j;
 scanf("%d %d",&v,&p);
 for (i=1; i<=v; i++) scanf("%ld",&d[i]);
 for (i=1; i<=v; i++)
  for (j=1; j<=p; j++) min[i][j]=MaxC;
 for (i=1; i<=v; i++)
  {min[i][1]=0;
   for (j=1; j<=i; j++) min[i][1]+=abs(d[j]-d[i/2+1]);
  }
}

void search()
{ int i,j,k,mid;
  long tmp;
 for (i=1; i<p; i++)
  for (j=1; j<=v; j++)
   if (min[j][i]!=MaxC)
    {mid=j; tmp=0;
     for (k=j+1; k<=v; k++)
      {if ((k-j)%2==1) mid++;
       tmp+=abs(d[k]-d[mid]);
       min[k][i+1]=MinNum(min[j][i]+tmp,min[k][i+1]);
      }
    }
 printf("%ld\n",min[v][p]);
}

int main()
{init();
 search();
 return 0;
}