糯米

TI DaVinci, gstreamer, ffmpeg
随笔 - 167, 文章 - 0, 评论 - 47, 引用 - 0
数据加载中……

POJ 2362 Square 搜索

题意:
给出N条木棍的长度,问能不能用这些木棍拼成一个正方形。


思路:
这题一开始想复杂了,后来发现只要2个最简单的剪枝题目就能79ms通过了。
再加上一个比较屌的剪枝就可以到16ms。
参考了网上的代码,很多份代码如出一辙。思想十分牛逼。



剪枝1:
所有木棍的长度必须能被4整除

剪枝2:
最长的木棍不能长于正方形的边长

这两个是最容易想到的,用上这两个可以79ms通过

剪枝3:
同样长度的木棍的同样数量的组合只搜索一次。
这个剪枝需要将木棍从大到小排列,在搜索的时候加一句代码就行了,代码很巧妙。
由于数据问题,这个剪枝貌似不管用。

剪枝4:
每条边的木棍按照从大到小的顺序拼接
如果某条木棍不能够作为某边的第一条木棍,那比它短的也不行
想一想还是可以理解,后面的边始终会用到这条长的棍子,那时候可供选择的木棍更少
所以在前面的边拼不成,在后面的边更加拼不成
这个剪枝非常牛逼,不知道谁想出来的,代码只需要一句。太牛逼了。
由于数据的N比较小,这个剪枝相当管用。

无法实现的理想化剪枝:
如果在枚举中,发现用一条长的棍子枚举失败,那么几条短的棍子组成同样长度的棍子也必然不用试验。
这个很理想,但是实现的代价很大。

#include <stdio.h>
#include 
<stdlib.h>
#include 
<string.h>

// 1+2 : 79ms
// 1+2+3 : 79ms
// 1+2+4 : 16ms
// 1+2+3+4: 16ms

int part, N;
int len[128];
char used[128];

int cmp(const void *a, const void *b)
{
    
return *(int *)b - *(int *)a;
}


int dfs(int side, int start, int left)
{
    
int i;

    
if (!left) {
        left 
= part;
        side
++;
        start 
= 0;
    }


    
if (side == 4)
        
return 1;

    
for (i = start; i < N; i++{
        
if (len[i] > left)
            
continue;
        
if (used[i])
            
continue;

        
// 3
        if (i && !used[i - 1&& len[i] == len[i - 1])
            
continue;

        used[i] 
= 1;
        
if (dfs(side, i + 1, left - len[i]))
            
return 1;
        used[i] 
= 0;

        
// 4
        if (left == part)
            
return 0;
    }


    
return 0;
}


int solve()
{
    
int i, sum;

    scanf(
"%d"&N);
    sum 
= 0;
    
for (i = 0; i < N; i++{
        scanf(
"%d"&len[i]);
        sum 
+= len[i];
    }


    
// 1
    if (sum % 4)
        
return 0;

    part 
= sum / 4;
    qsort(len, N, 
sizeof(len[0]), cmp);
    
// 2
    if (len[0> part)
        
return 0;

    memset(used, 
0, N);
    
return dfs(00, part);
}


int main()
{
    
int t;

    scanf(
"%d"&t);
    
while (t--
        printf(
"%s\n", solve() ? "yes" : "no");

    
return 0;
}




posted on 2010-10-04 13:08 糯米 阅读(977) 评论(0)  编辑 收藏 引用 所属分类: POJ


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