FZU 1005 Fast Food（dp）

题意：输入n，k，然后输入n个数，这n个数表示距离起点的距离，现在要选取k个点，使得距离和最小。

分析：我们求的是从n个点中选取k个点使得距离最小，即dp[n][k],那么dp[n][k]为dp[n-1][k-1]+sum[n][n],dp[n-2][k-1]+sum[n-1][n],dp[n-3][k-1]+sum[n-2][n]....dp[1][k-1]+sum[2][n]之间的最小值。

其中sum[x][y]表示从x点到y点在此区间选取一个点的最短距离（如果是个数是单数的话，选取中间那个点，偶数的话选取中间两个哪个都行）

记忆化搜索：

#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <stack>
using namespace std;

const int oo = 1e9;

int a[222];
int dp[222][33];
int sum[222][222];


int DFS(int n, int k)
{
    if(n<0||k<0)
        return oo;
    if(dp[n][k]!=-1)
        return dp[n][k];
    if(k>=n)
    {
        dp[n][k] = 0;
        return 0;
    }

    dp[n][k] = oo;
    for(int i=1; i<=n; i++)
    {
        dp[n][k] = min(dp[n][k], DFS(i-1, k-1)+sum[i][n]);//为前n个点建立k个点，可以由前1到n-1个点建立k-1个点推得，找到最优解。
    }
    return dp[n][k];
}

int main()
{
    int n, m;
    int kk = 1;
    while(scanf("%d%d", &n, &m), n+m)
    {
        a[0] = 0;
        for(int i=1; i<=n; i++)
        {
            scanf("%d", &a[i]);
        }
        for(int i=1; i<=n; i++)
        {
            sum[i][i] = 0;
            for(int j=i+1; j<=n; j++)
            {
                sum[i][j] = sum[i][j-1]+a[j]-a[(i+j)/2];//sum[i][j]表示在i，j之间选取一个点，消耗的最短距离（如果是单数的话，选取中间那个点，偶数的话选取中间两个哪个都行）
            }
        }
        memset(dp, -1, sizeof(dp));
        int ans = DFS(n, m);
        printf("Chain %d\n", kk++);
        printf("Total distance sum = %d\n\n", ans);
    }

    return 0;
}

dp

#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <stack>
using namespace std;

const int oo = 1e9;

int a[222];
int dp[222][33];
int sum[222][222];

int main()
{
    int n, m;
    int kk = 1;
    while(scanf("%d%d", &n, &m), n+m)
    {
        a[0] = 0;
        for(int i=1; i<=n; i++)
        {
            scanf("%d", &a[i]);
        }
        for(int i=1; i<=n; i++)
        {
            sum[i][i] = 0;
            for(int j=i+1; j<=n; j++)
            {
                sum[i][j] = sum[i][j-1]+a[j]-a[(i+j)/2];
            }
        }
        for(int i=0; i<=n; i++)
        {
            for(int j=0; j<=m; j++)
            {
                dp[i][j] = oo;
            }
        }
        dp[0][0] = 0;
        for(int i=1; i<=n; i++)
        {
            for(int k=1; k<=m; k++)
            {
                for(int j=0; j<i; j++)//此层循环和上层循环哪个在外面都可以，因为dp[i][k]只和 dp[1][k-1]到dp[i-1][k-1]之间的有关
                {
                    dp[i][k] = min(dp[i][k], dp[j][k-1]+sum[j+1][i]);//枚举从1到i-1之间的状态，进行更新dp[i][k]的值
                }
            }
        }
        printf("Chain %d\n", kk++);
        printf("Total distance sum = %d\n\n", dp[n][m]);
    }

    return 0;
}