问题描述:
给定n个点在直线上的距离,然后让你选择其中的p个点建立饭店,要求其他点都选择一家离自己最近的饭店供应,求总路程最短。
解题思路:
这道题目沉积很久了,去年就看到,但是一直不敢做,主要还是因为是DP,有点怕,寒假有一天拿过来做了一下,发现其实不是很难,于是开始推状态转移,当时的思路用是dp[i][j]表示第i个饭店建在第j个位置的最优解,想想没错,于是开始状态转移,中途需要一些辅助数组,dis[i][j]表示当饭店建在i点时,i~j之间所有点到i点的距离和,opt[i][j]表示当i和j均建立饭店时,两者之间的点取饭店的最小和,因为在i和j之间的点取的距离必定是两者的小值,于是可以统计出总和最小的值,于是就有状态转移方程
dp[i][j] = min{ dp[i-1][k] - dis[k][v] + dis[j][v] + opt[k][j], 1 <= k < j }
但是一直WA,就奇怪了,先放了一下。
今天再看一遍原来的代码,想了一下实在无懈可击了,于是开始检查代码,发现一个下标写错了,改了后就AC了,狂晕~~![](http://www.cppblog.com/Emoticons/QQ/icon18.gif)
代码如下:
#include <iostream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int line[301], v;
int p;
int dp[40][310]; //保存最优解
int route[40][310]; //记录路径
int dis[310][310]; //dis[i][j] 表示饭店建在i点时,i
j个点到达i点的总距离和
int opt[310][310]; //opt[i][j] 表示当i和j分别建立一个饭店时它们之间的饭店取向最优值
int cas;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int MIN(int a, int b)
{
return a < b ? a : b;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
//DP
int Solve()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int Min = -1;
int i, j, k;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 1; i <= v; i++)
{
dis[i][i] = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j = i-1; j >= 1; j--)
{
dis[i][j] = dis[i][j+1] + (line[i] - line[j]);
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j = i+1; j <= v; j++)
{
dis[i][j] = dis[i][j-1] + (line[j] - line[i]);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
memset(route, -1, sizeof(route));
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i = 1; i <= 30; i++)
for(j = 1; j <= 300; j++)
dp[i][j] = -1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 1; i <= v; i++)
{
dp[1][i] = dis[i][1] + dis[i][v];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(Min == -1 || dp[1][i] < Min)
Min = dp[1][i];
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(p == 1)
{
return Min;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
Min = -1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 1; i <= v; i++)
{
opt[i][i] = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j = i+1; j <= v; j++)
{
opt[i][j] = 100000000;
if(j == i + 1)
opt[i][j] = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{
for(k = i; k < j; k++)
opt[i][j] = MIN( opt[i][j], dis[i][k] + dis[j][k+1] );
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 2; i <= p; i++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j = 1; j <= v; j++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(k = 1; k < j; k++)
{
int buf;
buf = dp[i-1][k];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(buf < 0)
continue;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
buf -= dis[k][v];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
buf += dis[j][v];
buf += opt[k][j];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(buf < dp[i][j] || dp[i][j] == -1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
dp[i][j] = buf;
route[i][j] = k;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(i == p && dp[i][j] != -1)
{
if(dp[i][j] < Min || Min == -1)
Min = dp[i][j];
}
}
}
return Min;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int stack[100], top;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
//路径输出
void Output(int Value)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i, j, pre, next;
printf("Chain %d\n", cas++);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 1; i <= v; i++)
{
if(dp[p][i] == Value)
break;
}
pre = i;
top = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(pre != -1)
{
stack[ top++ ] = pre;
pre = route[p-top+1][pre];
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
next = v;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 0; i < top; i++)
{
printf("Depot %d at restaurant %d serves restaurant", i+1, stack[ i ]);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(i < top - 1)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(j = next; j >= 1; j--)
if(abs( line[j]-line[ stack[i] ] ) > abs( line[j]-line[ stack[i+1] ] ))
break;
if(j+1 == next)
printf(" %d\n", next);
else
printf("s %d to %d\n", j+1, next);
next = j;
}else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(next == 1)
printf(" %d\n", 1);
else
printf("s 1 to %d\n", next);
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf("Total distance sum = %d\n", Value);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i, j, k;
cas = 1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(scanf("%d %d", &v, &p) != EOF)
{
if(!v && !p) break;
for(i = 1; i <= v; i++)
scanf("%d", &line[i] );
Output(Solve());
puts("");
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)