首页 > ACM题库 > HDU-杭电 > hdu 2417 Kadj Squares[解题报告]C++
2014
01-26

hdu 2417 Kadj Squares[解题报告]C++

Kadj Squares

问题描述 :

In this problem, you are given a sequence S1, S2, …, Sn of squares of different sizes. The sides of the squares are integer numbers. We locate the squares on the positive x-y quarter of the plane, such that their sides make 45 degrees with x and y axes, and one of their vertices are on y=0 line. Let bi be the x coordinates of the bottom vertex of Si. First, put S1 such that its left vertex lies on x=0. Then, put S1, (i > 1) at minimum bi such that

bi > bi-1 and
the interior of Si does not have intersection with the interior of S1…Si-1.


The goal is to find which squares are visible, either entirely or partially, when viewed from above. In the example above, the squares S1, S2, and S4 have this property. More formally, Si is visible from above if it contains a point p, such that no square other than Si intersect the vertical half-line drawn from p upwards.

输入:

The input consists of multiple test cases. The first line of each test case is n (1 ≤ n ≤ 50), the number of squares. The second line contains n integers between 1 to 30, where the ith number is the length of the sides of Si. The input is terminated by a line containing a zero number.

输出:

The input consists of multiple test cases. The first line of each test case is n (1 ≤ n ≤ 50), the number of squares. The second line contains n integers between 1 to 30, where the ith number is the length of the sides of Si. The input is terminated by a line containing a zero number.

样例输入:

4
3 5 1 4
3
2 1 2
0

样例输出:

1 2 4
1 3

题意:(看图) 问从上往下看可以看到几个正方形,输出序号。。。纠结了好久,

找到每一个正方形的中点所在的横坐标,然后处理该正方形最左端到最右端的最高点, 最高点有更新则说明可以被看到,当然可能被后面的正方形覆盖。

为了处理方便,把变长都加倍了,原因(看下面的数据),自己画画就知道了。

提供测试数据:

6

4 1 1 1 1 5

6

5 1 1 1 1 4

5

4 1 1 1 4

0

答案:

1 3 6
1 4 6
1 5

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;
int m[129];
int v[3009];
int h[3009];
int re[109];
void solve(int n)
{
    memset(m,0,sizeof(m));
    memset(v,-1,sizeof(v));
    memset(h,0,sizeof(h));
    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=0;j<=re[i];j++)
        {
            t=max(t,j+m[j]);
        }
        for(int j=0;j<=re[i];j++)
        {
            m[j] = max(m[j],t+j);
            m[re[i]*2-j] = max(m[re[i]*2-j],t+j);
        }
        for(int j=t-re[i];j<=t+re[i];j++)
        {
            int hh = 2*re[i]-(t>j?t-j:j-t);
            if(hh>=h[j])
            {
                h[j] = hh;
                v[j] = i;
            }
        }
    }
    bool vv[59];
    memset(vv,0,sizeof(vv));
    for(int i=0;v[i]!=-1;i++)
    {
         vv[v[i]] = true;
    }
    bool ou = false;
    for(int i=0;i<n;i++)
    {
        if(vv[i])
        {
            if(ou) printf(" ");
            printf("%d",i+1);
            ou= true;
        }
    }
    printf("\n");
}
int main()
{
    freopen("in.txt","r",stdin);
    int n;
    while(~scanf("%d",&n)&&n)
    {
        for(int i=0;i<n;i++)
        scanf("%d",&re[i]),re[i]=re[i]*2;
        solve(n);
    }
    return 0;
}

解题转自:http://blog.csdn.net/binwin20/article/details/7855304


  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?