【POJ1160】Post Office(动态规划 DP)

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 04 月 26 日

题目给出一条直线上的m个村庄及其距离,给出n个邮局,要求怎么建n个邮局使代价最小。

思路:用opt[i][j]记录把前i个邮局建到前j个村庄中的最优解,用cost[i][j]记录所有在i到j村庄中,建1个邮局的最小代价。显然邮局应该设到中点。让前i个邮局覆盖前j个村庄,第i+1个邮局覆盖第j+1至j+k个村庄(j+k<=n),则状态转移方程为
res[i+1][j+k]=min{res[i][j]+cost[j+1][j+k];} (k+j<=n)

Cost数组存放从i到j中有一个邮局的最小代价,显然该邮局应该放在中间,构造cost的代码参考后边贴的代码。

样例数据:

 

Cost[i][j] 1 2 3 4 5 6 7 8 9 10
1 0 1 2 6 10 16 21 37 74 117
2   0 1 4 8 11 16 31 68 109
3     0 3 4 7 11 26 61 102
4       0 1 3 7 20 55 94
5         0 2 4 17 50 89
6           0 2 13 46 74
7             0 11 33 61
8               0 22 28
9                 0 6
10                   0

 

 

#include <iostream>  
using namespace std;  
int cost[302][302];  
int res[302][302];  
int village[302];  
inline int myabs(int a)  
{return a>0?a:-a;}  
int main(){freopen("1.txt","r",stdin);  
    int V,P,mid;  
    cin>>V>>P;  
    for (int i=1;i<=V;i++)  
        cin>>village[i];  
    for (int i=1;i<=V;i++){  
        for (int j=i;j<=V;j++){  
            mid=(i+j)>>1;  
            for (int k=i;k<=j;k++)  
                cost[i][j] +=myabs(village[mid]-village[k]);  
        }  
    }  
    //res[i][j] 表示前i个邮局覆盖前j个村庄的最小代价  
    for (int i=1;i<=V;i++)  
        res[1][i]=cost[1][i];  
    for (int i=2;i<=P;i++){  
        for (int j=1;j<=V;j++){  
            for (int k=1;k+j<=V;k++){  
                if(res[i][j+k]>res[i-1][j]+cost[j+1][j+k] || res[i][j+k]==0)  
                    res[i][j+k]=res[i-1][j]+cost[j+1][j+k];  
            }  
        }  
    }  
    cout<<res[P][V]<<endl;  
}  

 

res[i][j] 表示前i个邮局覆盖前j个村庄的最小代价,对于i=1来说,res[i][j] = cost[i][j],让前2个邮局覆盖前j个村庄,也就是i=2的情况,可能是一下情况的最优解:第一个邮局覆盖第一个村庄,第二个村庄覆盖2-j个村庄,或者第一个邮局覆盖第1-2个村庄,第二个村庄覆盖3-j个村庄,第一个邮局覆盖第1-3个村庄,第二个村庄覆盖4-j个村庄,等等等等。

 

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期五, 2017 年 12 月 15 日