usaco_4_1_2_fence8.cpp

usaco自己做的1到5章的代码

/*
TASK: fence8
LANG: C++
*/
/*
这道题真是相当恶心……
提交9次后终于过了，刚开始时的第4组数据~~o(∩_∩)o...哈哈，终于A掉了！ 
题目求能切出来的最多木料，而且木料不管长短，价值都是1，这样的多重背包看起来简单，遗憾的是50个包挑1023个东西，而且包的容量各不相同。
只能搜索。这里用到了以前没用到过的搜索方法，DFSID（Depth First with Iterative Deepening）
usaco在1.4的时候有提到过这种搜索方法，事实上就是当BFS空间不够时的一种用时间向空间妥协的方法。
迭代加深搜索的时间复杂度高于广搜，usaco的分析如下：
Depth First with Iterative Deepening (ID)
An alternative to breadth first search is iterative deepening. Instead of a single breadth first search, run D depth first searches in succession, each search allowed to go one row deeper than the previous one. That is, the first search is allowed only to explore to row 1, the second to row 2, and so on. This ``simulates'' a breadth first search at a cost in time but a savings in space. 

Complexity
The space complexity of iterative deepening is just the space complexity of depth first search: O(n). The time complexity, on the other hand, is more complex. Each truncated depth first search stopped at depth k takes ck time. Then if d is the maximum number of decisions, depth first iterative deepening takes c0 + c1 + c2 + ... + cd time. 

If c = 2, then this sum is cd+1 - 1, about twice the time that breadth first search would have taken. When c is more than two (i.e., when there are many choices for each decision), the sum is even less: iterative deepening cannot take more than twice the time that breadth first search would have taken, assuming there are always at least two choices for each decision. 

另外就是剪枝：
1.这道题由于木料的价值都是1，所以必然如果最大能切K个，则这K个木料必定是木料从小到大排序后的前K个。先把后面的那些剪掉 。
2.在分析搜索树时，搜索树越扁平，那么同样的剪枝效率越低，搜索树跟部越窄，剪枝效果越明显。所以我们把木料从大到小搜索，而木板从小到大搜索。
3.由于有重复的木料出现，那么在搜索的过程中，如果rail[i]==rail[i-1],而第i块木料在第K块木板上切的，那么第i-1块木料必定在大于等于K的木板上切出。这个方法可以剪掉很多！！
4.对于切剩下的board（无法再切下rail），统计一下总和。如果大于 board长度总和-rail长度总和，一定无解，可以剪枝。 
*/
#include<iostream>
#include <fstream>
#include <algorithm> 
using namespace std;
ifstream fin("fence8.in");
ofstream fout("fence8.out");

int nbd,nrail,best;
int board[51];
int rail[1024];
int rem[51];
int sumlen[1024];
long long sum=0;
long long maywaste,waste;
 
void DFS(int depth,int index)     
{
    if(depth == 0)
    {
        for(int i=index; i<nbd; ++i)
            if (rem[i]>=rail[0])
            {
                fout << best+1 << endl;
                fout.close();
                exit(0);
            }
        return;
    }
    for(int i=index; i<nbd; ++i)
        if(rem[i]>=rail[depth])
        {
            long long oldwaste=waste;
            rem[i]-=rail[depth];
            if (rem[i]<rail[0] && waste+rem[i]>maywaste)   //剪枝方法4 
            {
                rem[i]+=rail[depth];
                continue;
            }
            if (rem[i]<rail[0]) waste+=rem[i];
            if(rail[depth-1] == rail[depth]) DFS(depth-1,i);     //剪枝方法3 
            else DFS(depth-1,0);
            rem[i]+=rail[depth];
            waste=oldwaste;
        }
}
void DFSID(int nr)
{
     for(int i=nr-1;i>=0;--i){       //木料从大到小 
        waste=0;
        maywaste=sum-sumlen[i];   //记录木板的总长比木料总长多的值 
        best=i;
        DFS(i,0);
    }
}
int main()
{
    fin>>nbd;
    for(int i=0;i<nbd;i++){
        fin>>board[i];
        sum+=board[i];
        rem[i]=board[i];
    }
    fin>>nrail;
    for(int i=0;i<nrail;i++)
        fin>>rail[i];
    fin.close();
 
    sort(board,board+nbd);                           //剪枝方法2的排序 
    sort(rail,rail+nrail);
 
    int temp=0;
    sumlen[0]=rail[0];
    while(temp<nrail && sumlen[temp]<=sum){           //剪枝方法1 
         ++temp;
         sumlen[temp]=sumlen[temp-1]+rail[temp];
    }
    nrail=temp; 
    DFSID(nrail);
    fout<<'0'<<endl;
    return 0;
}