1 //Accepted    564 KB    63 ms 2 //和hdu1227一样 3 //dp[i][j]=min(dp[i][j],dp[k][j-1]+cost[k+1][i]) 4 //初始化条件，dp[0][0]=0; 5 //dp[i][0]=inf;i>=1; 6 #include <cstdio> 7 #include <cstring> 8 #include <iostream> 9 using namespace std;10 const int imax_n =305;11 const int imax_P = 35;12 const int inf = 100000000;13 int cost[imax_n][imax_n];14 int dp[imax_n][imax_P];15 int dis[imax_n];16 int n,P;17 int tabs(int x)18 {19     if (x<0) x=-x;20     return x;21 }22 int min(int a,int b)23 {24     return a<b?a:b;25 }26 void getCost()27 {28     for (int i=1;i<=n;i++)29     {30         for (int j=i;j<=n;j++)31         {32             cost[i][j]=0;33             int temp=(i+j)/2;34             for (int k=i;k<=j;k++)35             cost[i][j]+=tabs(dis[k]-dis[temp]);36         }37     }38 }39 void Dp()40 {41     getCost();42     for (int i=0;i<=n;i++)43     for (int j=0;j<=P;j++)44     dp[i][j]=inf;45     dp[0][0]=0;46     for (int i=1;i<=n;i++)47     {48         for (int j=1;j<=P && j<=i;j++)49         {50             for (int k=j-1;k<i;k++)51             {52                 dp[i][j]=min(dp[i][j],dp[k][j-1]+cost[k+1][i]);53             }54         }55     }56     printf("%d\n",dp[n][P]);57 }58 int main()59 {60     while (scanf("%d%d",&n,&P)!=EOF)61     {62         for (int i=1;i<=n;i++)63         scanf("%d",&dis[i]);64         Dp();65     }66     return 0;67 }

 1 //Accepted    564 KB    79 ms 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 using namespace std; 6 const int imax_n =305; 7 const int imax_P = 35; 8 const int inf = 100000000; 9 int cost[imax_n][imax_n];10 int dp[imax_n][imax_P];11 int dis[imax_n];12 int n,P;13 int tabs(int x)14 {15     if (x<0) x=-x;16     return x;17 }18 int min(int a,int b)19 {20     return a<b?a:b;21 }22 void getCost()23 {24     for (int i=1;i<=n;i++)25     {26         for (int j=i;j<=n;j++)27         {28             cost[i][j]=0;29             int temp=(i+j)/2;30             for (int k=i;k<=j;k++)31             cost[i][j]+=tabs(dis[k]-dis[temp]);32         }33     }34 }35 void Dp()36 {37     getCost();38     for (int i=0;i<=n;i++)39     dp[i][0]=inf;40     dp[0][0]=0;41     for (int i=1;i<=n;i++)42     {43         for (int j=1;j<=P && j<=i;j++)44         {45             dp[i][j]=inf;46             for (int k=j-1;k<i;k++)47             {48                 dp[i][j]=min(dp[i][j],dp[k][j-1]+cost[k+1][i]);49             }50         }51     }52     printf("%d\n",dp[n][P]);53 }54 int main()55 {56     while (scanf("%d%d",&n,&P)!=EOF)57     {58         for (int i=1;i<=n;i++)59         scanf("%d",&dis[i]);60         Dp();61     }62     return 0;63 }