hdu 1227 Fast Food(dp)

http://acm.hdu.edu.cn/showproblem.php?pid=1227

转载：

本来想做个图的，这样更清晰，我辛苦做出来的弄上面无法显示啊！我泪奔啊，我只能用汉字来说了，考验一下额的汉字表达水平！

• 仓库要建在商店的位置，也就是说，它一定在某个商店的坐标处；

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

const int INF = 0x3f3f3f3f;
int main()
{
    int n,k;
    int a[210];
    int cost[210][210];//cost[i][j]表示在i与j之间建仓库（在(i+j)/2处）的最小距离。
    int dp[35][210];//dp[i][j]表示前j个商店建i个仓库的最小距离。
    int item = 1;
    while(~scanf("%d %d",&n,&k))
    {
        if(n == 0 && k == 0) break;
        for(int i = 1; i <= n; i++)
            scanf("%d",&a[i]);
        memset(cost,0,sizeof(cost));
        for(int i = 1; i <= n-1; i++)
        {
            for(int j = i; j <= n; j++)
            {
                int mid = (i+j)/2;
                for(int k = i; k <= j; k++)
                    cost[i][j] += abs(a[mid]-a[k]); //若在i与j商店之间建仓库，应建在(i+j)/2处。
            }
        }
        for(int i = 1; i <= n; i++)
            dp[1][i] = cost[1][i];//切记初始化。

        for(int i = 2; i <= k; i++)
        {
            for(int j = i; j <= n; j++)
            {
                dp[i][j] = INF;
                for(int m = i-1; m <= j-1; m++)//枚举建前i-1个仓库时，商店数m的范围是 i-1 <= m <= j-1.
                    dp[i][j] = min(dp[i-1][m]+cost[m+1][j],dp[i][j]);
            }
        }

        printf("Chain %d\n",item++);
        printf("Total distance sum = %d\n\n",dp[k][n]);

    }
    return 0;
}

hdu 1227 Fast Food(dp),布布扣,bubuko.com

hdu 1227 Fast Food(dp)

原文：http://blog.csdn.net/u013081425/article/details/20486581