poj 1011 解题报告
昨天把1011AC了，不过还没有来得及写结题报告，占个位置先～
Source Code
| Problem: 1011 | User: omycle | |
| Memory: 264K | Time: 32MS | |
| Language: C++ | Result: Accepted |
- Source Code
#include <iostream>
#include <time.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
//#define GS 64
//#define GS 64//根数
//bool stt=false;
int GS;
int stick_length[50];//50就足够用了
int stick_count=0;//每一种可能的值对应的长棍的根数--是一个全局变量
int stick_length_count=0;// 有几种可能的长度值
int Len=0;//长度值的全局变量，利于递归访问
int * sticks_length;
//int sticks_length[10]={7,1,7,1,7,1,2,2,2,2};
/*
int sticks_length[64]={40,40,30,35,35,\
26,15,40,40,40,\
40,40,40,40,40,\
40,40,40,40,40,\
40,40,40,43,42,\
42,41,10,4,40,\
40,40,40,40,40,\
40,40,40,40,40,\
40,40,40,25,39,\
46,40,10,4,40,\
40,37,18,17,16,\
15,40,40,40,40,\
40,40,40,40};
*/
//bool flag[GS]={true};//全部可以用
bool * flag;
bool stick(int g_st,int length_ing,int next_gun);
//初始化flag[]
void Init_flag(int g)
{
memset(flag,true,sizeof(bool)*g);
}//---
//求出所有可能的结果
void mod(int n,int p)
{
int i=p;
int i_stick_length=0;
while(i<=n)
{
if(n%i==0)
{
stick_length[i_stick_length++]=i;
stick_length_count++;//The Stick可能的长度--每次计算出一个结果，可能的长度+1
}
i++;
}
}//---
//将小棍排序
void paixu(int *p)
{//用的是冒泡--要复习所有的排序算法
for(int i=0;i<GS-1;i++)
{
int j;
for(j=i+1;j<GS;j++)
{
if(p[i]<p[j])
{
int temp=p[i];
p[i]=p[j];
p[j]=temp;
}
}
}
}//---
void zuhe()
{
int Sum=0;
// Init_flag();
//先排序再说
paixu(sticks_length);
for(int i_sum=0;i_sum<GS;i_sum++)
{
Sum+=sticks_length[i_sum];//计算总长度
}
mod(Sum,sticks_length[0]);
for(int i=0;i<stick_length_count;i++)
{
Len=stick_length[i];
stick_count=Sum/Len;//每一种长棍情况对应的长棍的根数
if(stick(0,0,0))
break;
}
cout<<Len<<endl;
// cout<<"长度为"<<Len<<"共有多少"<<stick_count<<"根"<<endl;
}
bool stick(int g_st,int length_ing,int next_gun)//g_st:正在组第几根棍;length_ing:正在组合的长度;
{ //next_gun:下一根棍的索引
if(g_st==stick_count)
return true;
for(int i=next_gun;i<GS;i++)
{
if(flag[i])
{
int p=0;
if((p=length_ing+sticks_length[i])<Len)
{
flag[i]=false;
if(stick(g_st,p,i+1))
return true;//返回true 就说明i根能用了
else //如果第i+1根不成功,那么把i根给去掉，
{
flag[i]=true;
//length_ing-=sticks_length[i];
if(next_gun==0)//既：如果一直回溯到g_st=0说明这个Len不成功换下一组
break;
}
}
else if((p=length_ing+sticks_length[i])==Len)
{
flag[i]=false;
if(stick(g_st+1,0,0))
return true;
else
{
flag[i]=true;//如果stick(g_st+1,0,0) 不成功，那么就返回false
//return false;
break;
}
}
}
}
return false;
/*
//初始化flag[]
int Sum=0;
Init_flag();
//先排序再说
paixu(sticks_length);
for(int i_sum=0;i_sum<GS;i_sum++)
{
Sum+=sticks_length[i_sum];//计算总长度
}
mod(Sum,sticks_length[0]);
int i=0;
while(i<stick_length_count)
{
Init_flag();
stick_count=Sum/stick_length[i];
int i_s_q;
for( i_s_q=0;i_s_q<stick_count;i_s_q++)
{
int sum_length=0;
int i_s=0;//记录下面的细棍index
//是否等于小棍的长度，如果小于，加入；如果等于，加入；如果大于，继续后移动；
while(i_s<GS&&sum_length<stick_length[i])
{
if(flag[i_s]==true)
{
if(sum_length+sticks_length[i_s]<stick_length[i])//如果小于，那么加入
{
sum_length+=sticks_length[i_s];
flag[i_s]=false;//这根小棍不能再用了
}
else if(sum_length+sticks_length[i_s]==stick_length[i])
{
sum_length+=sticks_length[i_s];
flag[i_s]=false;
break;
}
}
i_s++;//根数后移，呵呵
}//--以上计算了是否等于长棍的长度
if(sum_length==stick_length[i])
{
//需要在外部循环做一下处理，就是表示已经兑好一根了，开始下一根吧
//ToDo:---
// i--;//即，还进行本组的组兑
// break;
if(i_s_q==stick_count-1)//因为i_s_q从0开始计数
{
cout<<"计算完成了!"<<endl;
cout<<"长度"<<stick_length[i]<<"的长棍，"<<stick_count<<"根"<<endl;
return ;
}
}
else if(i_s>=GS)
{
//这样，需要继续往后执行stick_length[]数组
//TODO:Here...
i++;
break;
}
}
}
if(i>=stick_length_count)
{
cout<<"我倒，有病啊，根本就不能算"<<endl;
return ;
}
*/
}
int main()
{
int f_n;
while(cin>>f_n)
{
GS=f_n;
if(f_n==0)
break;
sticks_length=(int *)malloc(f_n*sizeof(int));
flag=(bool *)malloc(f_n*sizeof(bool));
Init_flag(f_n);
for(int i=0;i<f_n;i++)
cin>>sticks_length[i];
zuhe();
free(sticks_length);
free(flag);
}
return 0;
}
ding～～
回复删除不错
回复删除