首页 > ACM题库 > HDU-杭电 > Hdu 1268 积木堆砌的城堡-动态规划[解题报告] C++
2013
12-04

Hdu 1268 积木堆砌的城堡-动态规划[解题报告] C++

积木堆砌的城堡

问题描述 :

一天,小希用积木搭了个城堡,并且照了正面和侧面的照片(前视图和右视图)给Gardon看,让Gardon猜猜她究竟用了多少块积木;Gardon发现从这两张照片上只能看出每一列上最高的地方有多高,但是无法推测出具体的形状(见图1、2),但是好在小希给了Gardon多次机会,所以Gardon只需要知道大概的范围就可以采用“二分查找”法来计算正确的结果。现在Gardon请你帮忙,根据这两张图,计算下最少和最多分别可能是多少块积木组成的,让他可以尽快的回答出小希的问题。

输入:

输入可能包含多组数据。每组数据的第一行分别有两个数:W和L(0<W,L<=100000),分别表示了该城堡前视图和右视图的宽度,接下来的W行,每行有一个数,第i行表示前视图中第i个位置的高度。同样,接下来的L行表示了该城堡的右视图,每行的一个数字表示了右视图对应位置的高度。
已知城堡最高不会超过5000个积木的高度。

输出:

对于每组数据,如果该城堡可能存在,输出两个数M和N(M,N<=10^14),表示最少可能的积木数和最多可能的积木数。如果该城堡不可能存在,输出"No solution."
注意积木不能悬空摆放。

样例输入:

4 3
1
3
4
2
1
4
2

样例输出:

10 21

#include<stdio.h>
#include<string.h>
#define i64 __int64
int Max(int a,int b){return a>b?a:b;}
int Min(int a,int b){return a<b?a:b;}
int n,m;

int main()
{
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        int hash[5555][2];
        int i,maxw,maxl,j;
        i64 a_min,a_max,temp;
        a_min=a_max=0;
        maxw=maxl=0;
        for(i=0;i<5555;i++)hash[i][0]=hash[i][1]=0;
        for(i=0;i<n;i++)
        {
            scanf("%d",&temp);
            maxw=Max(temp,maxw);
            hash[temp][0]++;
        }
        for(i=0;i<m;i++)
        {
            scanf("%d",&temp);
            maxl=Max(temp,maxl);
            hash[temp][1]++;
        }
        if(maxw!=maxl)
        {
            printf("No solution.\n");
            continue;
        }
        for(i=1;i<=maxw;i++)
        {
            if(hash[i][0]||hash[i][1])
            {
                a_min+=Max(hash[i][0],hash[i][1])*i;
            }
            temp=0;
            if(hash[i][0])
            {
                for(j=1;j<=maxl;j++)
                {
                    if(hash[j][1])temp+=Min(i,j)*hash[j][1];
                }
            }
            a_max+=temp*hash[i][0];
        }
        printf("%I64d %I64d\n",a_min,a_max);
    }
}

 


  1. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }