poj 1011

Sticks

Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 122529   Accepted: 28391

Description

George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.

Input

The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.

Output

The output should contains the smallest possible length of original sticks, one per line.

Sample Input

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

Sample Output

6
5

Source

Central Europe 1995

#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
const int maxn=80;

char g[maxn][maxn];

bool vis[maxn][maxn];

int dis[maxn][maxn];

int go[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

int x1,y1,x2,y2;

int w,h;

void bfs(int x,int y)
{
    queue <int> q;

    int tmp=x*(w+2)+y;

    q.push(tmp);

    vis[x][y]=true;

    while(!q.empty())
    {
        tmp=q.front();

        x=tmp/(w+2);

        y=tmp%(w+2);

        q.pop();

        if(x==x2 && y==y2) return;

        for(int i=0;i<4;i++)
        {
            int nx=x+go[i][0];
            int ny=y+go[i][1];

            while(nx>=0 && nx<=h+1 && ny>=0 && ny<=w+1 && !vis[nx][ny] && g[nx][ny]!=‘X‘)
            {
                tmp=nx*(w+2)+ny;
                vis[nx][ny]=true;
                dis[nx][ny]=dis[x][y]+1;
                q.push(tmp);
                nx=nx+go[i][0];
                ny=ny+go[i][1];
            }

        }
    }
}

int main()
{
int i;

    int k=0;

    while(scanf("%d%d",&w,&h)!=EOF && (w||h))
    {
        memset(g,0,sizeof(g));

        for(i=1;i<=h;i++)
        {
            getchar();

            for(int j=1;j<=w;j++)
                scanf("%c",&g[i][j]);
        }

        printf("Board #%d:\n",++k);

        int t=0;

        while(scanf("%d%d%d%d",&y1,&x1,&y2,&x2) && (x1||y1||x2||y2))
        {
            memset(vis,false,sizeof(vis));

            memset(dis,0,sizeof(dis));

            g[x2][y2]=0;

            bfs(x1,y1); 

            if(dis[x2][y2]==0)
printf("Pair %d: impossible.\n",++t);
            else
                printf("Pair %d: %d segments.\n",++t,dis[x2][y2]);

            g[x2][y2]=‘X‘;    //注意还原
        } 

        printf("\n");
    }
    return 0;
}

  

时间: 11-15

poj 1011的相关文章

POJ 1011 - Sticks DFS+剪枝

POJ 1011 - Sticks 题意:    一把等长的木段被随机砍成 n 条小木条    已知他们各自的长度,问原来这些木段可能的最小长度是多少 分析:    1. 该长度必能被总长整除    2. 从大到小枚举,因为小长度更灵活, 可拼接可不拼接    3. 因为每一跟木条都要用到, 故若轮到其中一根原始木段选它的第一根木条时,若第一根木条若不满足,则显然第一根木条在接下来任何一根原始木段都不会满足,故无解    4. 由于所有棒子已排序,在DFS时,若某根棒子未被选,则跳过其后面所有与

poj 1011 Sticks 【DFS】+【剪枝】

题意:有未知根(长度一样)木棒(小于等于n),被猪脚任意的截成n段,猪脚(脑抽了)想知道被截之前的最短长度(我推测猪脚得了健忘症). 这道题光理解题意就花了好久,大意就是任意根被截后的木棒拼到一起,能不能组成s(<=n)根的相同的木棒, 例:数据 9  5 1 2 5 1 2 5 1 2 可以组成最短为6 的(5+1, 2+2+2)3根木棒. 策略:深搜. 不过要是传统的深搜的话,TLE妥妥的.所以要剪枝(所谓剪枝,就是多加几个限制条件). 话不多说直接上代码. 代码1: #include <

[POJ 1011]Sticks(DFS剪枝)

Description George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were original

POJ 1011 Sticks 【DFS 剪枝】

题目链接:http://poj.org/problem?id=1011 Sticks Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 154895   Accepted: 37034 Description George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now

POJ 1011 Sticks dfs,剪枝 难度:2

http://poj.org/problem?id=1011 要把所给的集合分成几个集合,每个集合相加之和ans相等,且ans最小,因为这个和ans只在[1,64*50]内,所以可以用dfs一试 首先ans需要满足两个条件1.可以被总集合的和sum整除 2.是总集合的某个子集的和 对于条件1,可以通过试除遍历 对于条件2,可以通过dp预筛选,这两个花费时间都不大 接着搜索能不能划分成集合之和恰为ans的若干集合, 1. 可以从大向小找,因为大的更不灵活,而且所有的元素都需要取到 2.比如对于5,

POJ 1011 递归 &amp; 回溯

题目大意:给出一些长度不大于 50 的木棍, 要求你把这些小木棍拼成*             长度相同木棍,当然长度越小越好.* 解题思路:这个题最近做了很多次,我比较有发言权了.*             思想很简单,一个接一个的把木棍拼起来,最后把木棍用光.*             关键的地方是几个剪枝技巧:*                   设所有木棍的总长度为 Sum, 最终的答案是 L. *             1. 首先要明白, Sum一定要能被 L 整除. *     

poj 1011/2362 dfs+剪枝(拼木棍)

题意:乔治拿来一组等长的木棒,将它们随机地砍断,使得每一节木棍的长度都不超过50个长度单位.然后他又想把这些木棍恢复到为裁截前的状态,但忘记了初始时有多少木棒以及木棒的初始长度.请你设计一个程序,帮助乔治计算木棒的可能最小长度.每一节木棍的长度都用大于零的整数表示.(2362是1011的特例,问一堆木棍能否拼成正方形) 思路:dfs+剪枝.其中剪枝具有相当的技巧性,其中一个地方的剪枝没有想到导致tle多次. 几个明显的剪枝点(设ans为最终的答案): 1.ans>=这堆木棍的最大长度 2.ans

poj 1011 Sticks ,剪枝神题

木棒 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 118943 Accepted: 27429 Description 乔治拿来一组等长的木棒.将它们随机地砍断.使得每一节木棍的长度都不超过50个长度单位.然后他又想把这些木棍恢复到为裁截前的状态,但忘记了初始时有多少木棒以及木棒的初始长度.请你设计一个程序,帮助乔治计算木棒的可能最小长度.每一节木棍的长度都用大于零的整数表示. Input 输入包括多组数据,每组数据包括两

POJ 1011 sticks 搜索

Sticks Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 125918   Accepted: 29372 Description George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the or

POJ 1011 Sticks

DFS 题意是让你把这些木棍组合成长度相等的一些木棍.要求长度最短. #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; int a[65],n,sum,ans; bool v[65],ok; bool cmpa(int a,int b) { return a>b; } bool dfs(int num,int need,