poj1160 动态规划

#include<stdio.h>
#include<string.h>
#define INF 999999999
#define Min(x,y) (x<y?x:y)
#define max 300+5
//dp[i][k]记录在从1到i的村庄中放置k个邮局的最短总距离
//sum[i][j]记录在从第i到第j个村庄中放置一个邮局的最短总距离
int dp[max][30+5],sum[max][max];
int n,m,x[max];

int main(){
    while(~scanf("%d%d",&n,&m)){
        for(int i=1;i<=n;i++){
            scanf("%d",&x[i]);
        }
        memset(sum,0,sizeof(sum));
        for(int i=1;i<n;i++){
            for(int j=i+1;j<=n;j++){
                //最优的方案肯定是将邮局放在中间的村庄中
                sum[i][j]=sum[i][j-1]+x[j]-x[(j+i)/2];
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                dp[i][j]=INF;
            }
            dp[i][1]=sum[1][i];
        }
        for(int k=2;k<=m;k++){
            for(int i=k;i<=n;i++){
                int res=INF;
                for(int j=k-1;j+1<=i;j++){
                    //转移方程在前j个村庄中放置k-1个邮局的最短距离+在从第j+1到第i个村庄中放1个邮局的最短距离,后者就是sum[j+1][i]
                    res=Min(res,dp[j][k-1]+sum[j+1][i]);
                }
                dp[i][k]=res;
            }
        }
        printf("%d
",dp[n][m]);
    }
}