USACO 4-1-2 Fence Rails

/
ID:qcx97811
LANG:C
TASK:fence8
/
#include
#include

int board[56],rail[1026],rail_sum[1026];
int N,R,bsum,up

//排序用的模板
int cmp(const void a,const void b)
{
if((int )a > (int )b)
return 1
if((int )a == (int )b)
return 0
return -1
}

int work(int total,int rstart,int bstart)
{//total是到当前已经浪费掉的木板长度
//rstart更准确的是rend也就是当前的最大rail下标 因为是从大到小
//bstart是当前从哪块board开始的
int i
int t_bstart,t_total
t_total = 0
if(-1 == rstart)//表示搜索已经结束了
return 1
for(i = N-1i >;= bstart;i–)
{//搜索 从大到小
if(board[i] >= rail[rstart])
{//如果可以从这个board上切的话
board[i] -= rail[rstart];//更新board
if(board[i] < rail[0])
{//如果这个board已经不可能再切出其他rail了
t_total = total+board[i];//更新浪费的board总数
if(t_total+rail_sum[up] > bsum)
{//如果已经不可能切出up+1[搜索的是下标]个rail
board[i] += rail[rstart];//回溯
continue//进行下次个搜索
}
}
else
t_total = total//浪费的board
if(rstart > 0 & (rail[rstart-1] == rail[rstart]))
t_bstart = i//如果下一块rail和当前的rail相等
//那么下一块rail所对应的board一定比当前rail所对应的
//board的下标要大 至少不会小
else
t_bstart = 0//board的最小下标为0 这里不用考虑某块board已经被用 因为每次都会更新board的大小
if(1 == work(t_total,rstart-1,t_bstart))
return 1//如果搜索成功的话 就返回成功
board[i] += rail[rstart];
}
}
return 0
}
int main(void)
{
freopen(“fence8.in”,“r”,stdin);
freopen(“fence8.out”,“w”,stdout);
int i
scanf(“%d”,N);//N是board的数目
bsum = 0//bsum用来记录所有board的总和 用于一个小剪枝
for(i = 0i < N;i++)
{
scanf(“%d”,board[i]);
bsum += board[i];
}
scanf(“%d”,R);//R是rail的的总数
for(i = 0i < R;i++)
{
scanf(“%d”,rail[i]);
}
qsort(board,N,sizeof(board[0]),cmp);
qsort(rail,R,sizeof(rail[0]),cmp);
//对board数组和rail数组进行从小到大的排序
//下面的rail_sum数组表示从rail[0]加到rail[i]的总和 也是用于剪枝
rail_sum[0] = rail[0];
for(i = 1i < R;i++)
{
rail_sum[i] = rail_sum[i-1] + rail[i];
}
up = R-1//up是有可能的最大下标
while(rail_sum[up] > bsum)
up–
#if 0
用于调试
printf(“%d\n”,up);
#endif
while(0 == work(0,up,0))//搜索结果
up–
printf(“%d\n“,up+1);//由于搜索出来的是下标 所以结果得+1
return 0
}