poj 1011 hdoj 1455 Sticks（搜索+剪枝）
poj 1011 hdoj 1455 Sticks（搜索+剪枝）
xindoo
发布于 2021-01-22 12:51:36
发布于 2021-01-22 12:51:36
大致题意：
有n跟棍， 求它们能组成最短且长度相同的棍的长度
解题思路：
DFS+剪枝
POJ2362的强化版，重点在于剪枝 建议你先看看这道题 here
令initlen为所求的最短原始棒长，maxlen为给定的棒子堆中最长的棒子，sumlen为这堆棒子的长度之和，那么initlen必定在范围[maxlen，sumlen]中，
cnt为可能组成的数目，也就是sunlen/maxlen。
根据棒子的灵活度（棒子越长，灵活度越低） DFS前先对所有棒子降序排序
剪枝：
1、 由于所有原始棒子等长，那么必有sumlen%Initlen==0，这个我在main函数中做了。
2、 若能在[maxlen,sumlen-InitLen]找到最短的InitLen，该InitLen必也是[maxlen,sumlen]的最短；若不能在[maxlen,sumlen-InitLen]找到最短的InitLen，则必有InitLen=sumlen；
3、 由于所有棒子已降序排序，在DFS时，若某根棒子不合适，则跳过其后面所有与它等长的棒子；
4、 最重要的剪枝：对于某个目标InitLen，在每次构建新的长度为InitLen的原始棒时，检查新棒的第一根stick[i]，若在搜索完所有stick[]后都无法组合，则说明stick[i]无法在当前组合方式下组合，不用往下搜索(往下搜索会令stick[i]被舍弃)，直接返回上一层
代码
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
bool vis[65];
int stick[65];
int n, initlen, cnt;
bool cmp(int x, int y)
{
return x > y;
}
bool dfs(int num, int len, int s)//s为搜索起点
{
if (num == cnt)
return true;
int same = -1;
for (int i = s; i < n; i++)
{
if (vis[i] || stick[i] == same) //剪枝3
continue;
vis[i] = true;
if (len+stick[i] < initlen)
{
if (dfs(num, len+stick[i], i))
return true;
else
same = stick[i];
}
else if (len+stick[i] == initlen)
{
if (dfs(num+1, 0, 0))
return true;
else
same = stick[i];
}
vis[i] = false;
if (len == 0) //剪枝4
break;
}
return false;
}
int main()
{
while (scanf("%d", &n) && n)
{
int sumlen = 0;
int maxlen = 0;
for (int i = 0; i < n; i++)
{
scanf("%d", &stick[i]);
sumlen += stick[i];
if (stick[i] > maxlen)
maxlen = stick[i];
}
sort(stick, stick+n, cmp);
for (initlen = maxlen; initlen <= sumlen; initlen++)// 剪枝1
{
if (sumlen%initlen) //剪枝2
continue;
cnt = sumlen/initlen;
memset(vis, false, sizeof(vis));
if (dfs(1, 0, 0))
{
printf("%d\n", initlen);
break;
}
}
}
return 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2013-04-30，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读