Source Code

 Problem:         User: sdfzyhy

 Memory: 1108K        Time: 0MS

 Language: G++        Result: Accepted

     Source Code

     //POJ 1160

     #include<cmath>

     #include<vector>

     #include<cstdio>

     #include<cstring>

     #include<cstdlib>

     #include<iostream>

     #include<algorithm>

     #define rep(i,n) for(int i=0;i<n;++i)

     #define F(i,j,n) for(int i=j;i<=n;++i)

     #define D(i,j,n) for(int i=j;i>=n;--i)

     #define pb push_back

     using namespace std;

     int getint(){

         int v=,sign=; char ch=getchar();

         while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}

         while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}

         return v*=sign;

     }

     typedef long long LL;

     /******************tamplate*********************/

     const int N=,INF=~0u>>;

     int dp[][N],s[][N],w[N][N],a[N],n,m;

     int main(){

     #ifndef ONLINE_JUDGE

         freopen("1160.in","r",stdin);

         freopen("1160.out","w",stdout);

     #endif

         n=getint(); m=getint();

         F(i,,n) a[i]=getint();

         F(i,,n){

             w[i][i]=;

             F(j,i+,n) w[i][j]=w[i][j-]+a[j]-a[(i+j)>>];

         }

         F(i,,n) F(j,,m) dp[j][i]=INF;

         F(i,,n){

             dp[][i]=w[][i];

             s[][i]=;

         }

         F(i,,m){

             s[i][n+]=n;

             D(j,n,i+)

                 F(k,s[i-][j],s[i][j+])

                     if (dp[i-][k]+w[k+][j]<dp[i][j]){

                         s[i][j]=k;

                         dp[i][j]=dp[i-][k]+w[k+][j];

                     }

         }

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

         return ;

     }