UC知道各位能指点一下我pku1011棍子吗？
来源：百度知道 编辑：UC知道 时间：2024/06/23 07:43:14
题目：http://acm.pku.edu.cn/JudgeOnline/problem?id=1011
#include "iostream"
#include "stdlib.h"
#include "string.h"
using namespace std;
int stick[100],tag[100];
int target,n,flag,mark;
int cmp(const void *a,const void *b)
{
return *(int *)b-*(int *)a;
}
int dfs(int target,int num,int len)
{
int i;
if(num==0)
{
flag=1;
return 1;
}
for(i=0;i<n;i++)
{
if(tag[i] == 1 || len+stick[i] > target)
continue;
if(stick[i]==stick[mark]) /*这个if我是想同长度的棍子，以前找过，下次就不找了*/
continue;
if(len+stick[i]==target)
{
tag[i]=1;
num--;
if(dfs(target,num,0)==1)
break;
num++;
tag[i]=0;
mark=i;
}
else if(len+stick[i]<target)
#include "iostream"
#include "stdlib.h"
#include "string.h"
using namespace std;
int stick[100],tag[100];
int target,n,flag,mark;
int cmp(const void *a,const void *b)
{
return *(int *)b-*(int *)a;
}
int dfs(int target,int num,int len)
{
int i;
if(num==0)
{
flag=1;
return 1;
}
for(i=0;i<n;i++)
{
if(tag[i] == 1 || len+stick[i] > target)
continue;
if(stick[i]==stick[mark]) /*这个if我是想同长度的棍子，以前找过，下次就不找了*/
continue;
if(len+stick[i]==target)
{
tag[i]=1;
num--;
if(dfs(target,num,0)==1)
break;
num++;
tag[i]=0;
mark=i;
}
else if(len+stick[i]<target)
因为没有编译器，所以没法帮你调程序啦
我先帮你找一个错误：全局的mark肯定不对了
因为题目当中描述最长的stick可能是50，所以你可以设一个数组，第k个元素存放的是长度为k的stick剩下多少根，这样如果搜索当中碰到剩下的元素正好能用一根stick的话就会减少好多搜索量
另外 for(i=stick[0];i<=sum;i++)
这句话 也是很影响速度的一句话 一定要弄成倍数会好很多
下面附一下我曾经A的code 很早以前写的 仅供参考
Source Code
Problem: 1011 User: rooke
Memory: 152K Time: 15MS
Language: C++ Result: Accepted
Source Code
#include <iostream>
#define def_max 70
#define data_max 55
using namespace std;
int cutstack[def_max][def_max];
int a[data_max],lpt,totl,ok;
void trya(int stith);
void tryb(int maxlen,int uplen,int stith,int compa,int height)
{
int i;
if (maxlen==0)
{
trya(stith-1);
return;
}
else
{
for (i=uplen;i>=1;i--)
if (i<=maxlen&&a[i]>0)
if (compa||i<=cutstack[stith+1][height])
{
if (ok) return;
cuts