noi 162 post office dp

大致题意：

有v个村庄，每个村庄有各自的位置，且每个位置互不相同。现在要在村庄上设立P个邮局，使每个村庄到最近的邮局的距离之和最小。

分析：

定义状态d[i][j]表示前i个村庄，在这i个村庄中设立j个邮局的最小距离。s[i][j]表示村庄i至村庄j这几个村庄中设立一个邮局的最小距离。如果设立一个邮局，那么邮局设立在(a+b)/2这个位置是最优的。所以可以分解成以下子问题：

d[i][j]的最小值为d[k][j-1]的最小值加上s[k+1][i]，s[k+1][i]为在k+1至i这几个村庄中设立一个邮局的最小距离。

d[i][j]=min(d[i][j], d[k][j-1]+s[k+1][i])

边界条件d[i][1]=s[1][i].

s数组可做如下优化：

s[1][4]，把邮局设立在2和设立在3上距离是相同的。x2-x1+x3-x2+x4-x2与x3-x1+x3-x2+x4-x3相等。s[1][5]是把邮局设立在3上，s[1][5]=s[1][4]+x[5]-x[3]。由此，可得出递推式：s[i][j]=s[i][j-1]+x[j]-x[(i+j)/2].

#include <iostream>

#include <cstdio>

using namespace std;

const int INF=1e8;

int x[305];

int d[305][35];

int s[305][305];

int main()

{

    //freopen("in.txt","r",stdin);

    int n,p;

    while(~scanf("%d%d",&n,&p))

    {

        for(int i=1;i<=n;i++)

            scanf("%d",&x[i]);

        for(int i=1;i<=n;i++)

            for(int j=1;j<i && j<=p;j++)

                d[i][j]=INF;

        for(int i=1;i<=n;i++)

        {

            for(int j=i+1;j<=n;j++)

                s[i][j]=s[i][j-1]+x[j]-x[(i+j)/2];

            d[i][1]=s[1][i];

        }

        for(int i=2;i<=n;i++)

            for(int j=2;j<=i && j<=p;j++)

                for(int k=j-1;k<i;k++)

                    d[i][j]=min(d[i][j],d[k][j-1]+s[k+1][i]);

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

    }

    return 0;

}

巴特西

noi 162 post office dp

最新文章

热门文章