随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

Pku 1485 Fast food(DP)

问题描述:
给定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了,狂晕~~


代码如下:

#include <iostream>

using namespace std;

int line[301], v;
int p;
int dp[40][310];           //保存最优解
int route[40][310];        //记录路径
int dis[310][310];         //dis[i][j] 表示饭店建在i点时,ij个点到达i点的总距离和
int opt[310][310];         //opt[i][j] 表示当i和j分别建立一个饭店时它们之间的饭店取向最优值
int cas;

int MIN(int a, int b){
    
return a < b ? a : b;
}


//DP
int Solve()
{
    
int Min = -1;
    
int i, j, k;
    
for(i = 1; i <= v; i++){
        dis[i][i] 
= 0;
        
for(j = i-1; j >= 1; j--){
            dis[i][j] 
= dis[i][j+1+ (line[i] - line[j]);
        }

        
for(j = i+1; j <= v; j++){
            dis[i][j] 
= dis[i][j-1+ (line[j] - line[i]);
        }

    }


    memset(route, 
-1sizeof(route));

    
for(i = 1; i <= 30; i++)
        
for(j = 1; j <= 300; j++)
            dp[i][j] 
= -1;

    
for(i = 1; i <= v; i++){
        dp[
1][i] = dis[i][1+ dis[i][v];

        
if(Min == -1 || dp[1][i] < Min)
            Min 
= dp[1][i];
    }


    
if(p == 1){
        
return Min;
    }


    Min 
= -1;

    
for(i = 1; i <= v; i++){
        opt[i][i] 
= 0;
        
for(j = i+1; j <= v; j++){
            opt[i][j] 
= 100000000;
            
if(j == i + 1)
                opt[i][j] 
= 0;
            
else {
                
for(k = i; k < j; k++)
                    opt[i][j] 
= MIN( opt[i][j], dis[i][k] + dis[j][k+1] );
            }

        }

    }




    
for(i = 2; i <= p; i++){
        
for(j = 1; j <= v; j++){
            
for(k = 1; k < j; k++){
                
int buf;
                buf 
= dp[i-1][k];

                
if(buf < 0)
                    
continue;

                buf 
-= dis[k][v];

                buf 
+= dis[j][v];
                buf 
+= opt[k][j];

                
if(buf < dp[i][j] || dp[i][j] == -1)
                
{
                    dp[i][j] 
= buf;
                    route[i][j] 
= k;
                }

            }


            
if(i == p && dp[i][j] != -1){
                
if(dp[i][j] < Min || Min == -1)
                    Min 
= dp[i][j];
            }

        }

    }

    
return Min;
}


int stack[100], top;

//路径输出
void Output(int Value)
{
    
int i, j, pre, next;
    printf(
"Chain %d\n", cas++);

    
for(i = 1; i <= v; i++){
        
if(dp[p][i] == Value)
            
break;
    }

    pre 
= i;
    top 
= 0;
    
while(pre != -1){
        stack[ top
++ ] = pre;
        pre 
= route[p-top+1][pre];
    }


    next 
= v;
    
for(i = 0; i < top; i++){
        printf(
"Depot %d at restaurant %d serves restaurant", i+1, stack[ i ]);

        
if(i < top - 1){

            
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
        
{
            
if(next == 1)
                printf(
" %d\n"1);
            
else
                printf(
"s 1 to %d\n", next);
        }


    }


    printf(
"Total distance sum = %d\n", Value);
}


int main()
{
    
int i, j, k;
    cas 
= 1;
    
while(scanf("%d %d"&v, &p) != EOF){
        
if(!&& !p) break;
        
for(i = 1; i <= v; i++)
            scanf(
"%d"&line[i] );
        Output(Solve());
        puts(
"");
    }

    
return 0;
}

posted on 2009-02-20 23:07 英雄哪里出来 阅读(394) 评论(0)  编辑 收藏 引用 所属分类: ACM


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理