首页 > ACM题库 > HDU-杭电 > hdu 1942 Pizza delivery-动态规划-[解题报告]C++
2013
12-26

hdu 1942 Pizza delivery-动态规划-[解题报告]C++

Pizza delivery

问题描述 :

Your Irish pizza and kebab restaurant is doing very well. Not only is the restaurant full almost every night, but there is also an ever increasing number of deliveries to be made, all over town. To meet this demand, you realize that it will be necessary to separate the delivery service from the restaurant. A new large kitchen, only for baking pizzas and being a base for deliveries, has to be established somewhere in town. The main cost in the delivery service is not the making of the pizza itself, but the time it takes to deliver it. To minimize this, you need to carefully plan the location of the new kitchen. To your help you have a database of all last year’s deliveries. For each block in the city, you know how many deliveries were made there last year. The kitchen location will be chosen based on the assumption that the pattern of demand will be the same in the future.
Your city has a typical suburban layot � an orthogonal grid of equalsize square blocks. All places of interest (delivery points and the kitchen) are considered to be located at street crossings. The distance between two street crossings is the Manhattan distance, i.e., the number of blocks you have to drive vertically, plus the number of blocks you have to drive horizontally. The total cost for a delivery point is its Manhattan distance from the kitchen, times the number of deliveries to the point. Note that we are only counting the distance from the kitchen to the delivery point.
Even though we always drive directly back to the kitchen after a delivery is made, this (equal) distance is not included in the cost measure.

输入:

On the rst line, there is a number, 1 <=n <=20, indicating the number of
test cases. Each test case begins with a line with two integers, 1 <= x <= 100, 1<= y <= 100, indicating the size of the two-dimenstional street grid. Then follow y lines, each with x integers, 0<= d <=1000, indicating the number of deliveries made to each street crossing last year.

输出:

On the rst line, there is a number, 1 <=n <=20, indicating the number of
test cases. Each test case begins with a line with two integers, 1 <= x <= 100, 1<= y <= 100, indicating the size of the two-dimenstional street grid. Then follow y lines, each with x integers, 0<= d <=1000, indicating the number of deliveries made to each street crossing last year.

样例输入:

2
4 4
0 8 2 0
1 4 5 0
0 1 0 1
3 9 2 0
6 7
0 0 0 0 0 0
0 1 0 3 0 1
2 9 1 2 1 2
8 7 1 3 4 3
1 0 2 2 7 7
0 1 0 0 1 0
0 0 0 0 0 0

样例输出:

55 blocks
162 blocks

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[16][16][16];
int g[51][16][16][16];
int c1[51],c2[51],c3[51];
int ans[51],len;
int main()
{
    int n,r1,r2,r3;
    while(scanf("%d %d %d",&r1,&r2,&r3)==3)
    {
        if(r1==0 && r2==0 && r3==0)
            break;
        len=0;
        memset(dp,0,sizeof(dp));
        memset(g,0,sizeof(g));
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
            scanf("%d %d %d",&c1[i],&c2[i],&c3[i]);
        for(int i=1; i<=n; i++)
            for(int t1=r1; t1>=0; t1--)
                for(int t2=r2; t2>=0; t2--)
                    for(int t3=r3; t3>=0; t3--)
                        if(t1-c1[i]>=0 && t2-c2[i]>=0 && t3-c3[i]>=0)
                        {
                            dp[t1][t2][t3]=dp[t1][t2][t3];
                            if(dp[t1-c1[i]][t2-c2[i]][t3-c3[i]]+1>dp[t1][t2][t3])
                            {
                                dp[t1][t2][t3]=dp[t1-c1[i]][t2-c2[i]][t3-c3[i]]+1;
                                g[i][t1][t2][t3]=true;
                            }
                        }
        if(dp[r1][r2][r3])
        {
            printf("%d\n",dp[r1][r2][r3]);
            while(n!=0)
            {
                if(g[n][r1][r2][r3])
                {
                    ans[len++]=n;
                    r1-=c1[n];
                    r2-=c2[n];
                    r3-=c3[n];
                }
                n--;
            }
            sort(ans,ans+len);
            for(int i=0; i<len; i++)
            {
                if(i)
                    printf(" ");
                printf("%d",ans[i]);
            }
            printf("\n");
        }
        else
            printf("0\n");
    }
    return 0;
}

解题转自:http://www.cnblogs.com/luyi0619/archive/2010/09/08/1821813.html


  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。