题目含义
v 个村庄要建 p 个邮局
现给出每个村庄的位置, 并且邮局只能建在村庄的位置
问每个村庄到离它最近的邮局距离之和最小为多少
题目分析
区间 dp[i][j] 表示在前 i 个村庄建 j 个邮局的最小距离
dp[i][j]=min(dp[i][j],dp[k][j-1]+dis[k+1][j])
这个状态方程表示, 将 [在前 i 个村庄建 j 个邮局的距离] 划分成 [在前 k 个村庄建 j-1 个邮局的距离] 加上 [在第 k+1 个村庄到第 j 个村庄之间建一个邮局的距离]
题目代码
- #include
- #include
- #include
- #include
- using namespace std;
- typedef long long LL;
- const int INF=0x3f3f3f3f;
- int v,p;
- int a[307],dis[307][307],dp[307][307];
- int main(){
- scanf("%d%d",&v,&p);
- for(int i=1;i<=v;i++){
- scanf("%d",&a[i]);
- }
- memset(dis,0,sizeof(dis));
- for(int i=1;i<=v;i++)
- for(int j=i+1;j<=v;j++){
- dis[i][j]=dis[i][j-1]+a[j]-a[(i+j)/2];
- }
- memset(dp,INF,sizeof(dp));
- for(int i=1;i<=v;i++){
- dp[i][i]=0;
- dp[i][1]=dis[1][i];
- }
- for(int j=2;j<=p;j++)
- for(int i=j+1;i<=v;i++){
- for(int k=j-1;k<i;k++)
- dp[i][j]=min(dp[i][j],dp[k][j-1]+dis[k+1][i]);
- }
- printf("%d\n",dp[v][p]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3134425.html