終于做到的C4，然而基礎(chǔ)的不牢固致使C4做的這么艱難。基本上攙扶著做了這節(jié)的題，搜索剪枝啊，確實(shí)是門學(xué)問，而且搜索經(jīng)常寫做，得不出結(jié)果，郁悶。

Beef McNuggets (nuggets)
動態(tài)規(guī)劃，需要做一下預(yù)處理，找兩個(gè)最小的互質(zhì)的數(shù)之積作為搜索上界。如果a，b互質(zhì)，則ax+by=有>=a*b的整數(shù)解，這樣就很快了。

Fence Rails (fence8)
參考了Qinz牛的blog，需要很多剪枝，這里用到了一個(gè)叫dfsid的迭代加深搜索算法，大意是dfs過程中如果求最短，就由淺至深增加深度直至找到解，此題是由深至淺，如果找到解就輸出，否則深度減少。
dfsid偽代碼如下：

DFSID
procedure dfs(depth:longint);
　begin
　　if 要剪枝 then exit;
　　if 可行 then Print;
　　if Depth<MaxDepth then dfs(depth+1);
　end;

procedure Iterative_Deepening;
　begin
　　MaxDepth:=0;
　　while true do
　　　begin
　　　　inc(MaxDepth);
　　　　dfs(1);
　　　end;
　end;

Fence Loops (fence6)
這題求最小環(huán)，我圖論學(xué)的少，所以就搜索著做的，搜索的時(shí)候是兩個(gè)方向，建立模型的時(shí)候有點(diǎn)兒技巧，沒有什么剪枝就能過。
另外可以用dijkstra做，對每條邊先去掉，求最短路徑，再加上這條邊，取最小值。
我覺得這個(gè)代碼不錯(cuò)，把邊轉(zhuǎn)化成點(diǎn)做的，程序很簡潔，分享代碼：

Dijkstra
Dijkstra
#include <stdio.h>
#define MAX 30000
 
int n;
int len[101];
int map[2][101][8];
 
void pre(){
    int i,j,k;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&j);
        scanf("%d",&len[j]);
        scanf("%d%d",&map[0][j][0],&map[1][j][0]);
        for(k=1;k<=map[0][j][0];k++)scanf("%d",&map[0][j][k]);
        for(k=1;k<=map[1][j][0];k++)scanf("%d",&map[1][j][k]);
    }
}
 
int dis[101];
int isi[101];
int bef[101];
 
int dijkstra(int z){
    int i,j,k;
    for(i=1;i<=n;i++){dis[i]=MAX;isi[i]=0;}
    for(i=1;i<=map[0][z][0];i++){bef[map[0][z][i]]=z;dis[map[0][z][i]]=len[z];}
    while(1){
        j=0;k=MAX;
        for(i=1;i<=n;i++)
            if(dis[i]<k && isi[i]==0){
                j=i;
                k=dis[i];
            }
        if(j==0)break;
        if(j==z)return dis[z];
        isi[j]=1;
        for(i=1;i<=map[0][j][0];i++)
            if(map[0][j][i]==bef[j])break;
        if(i==map[0][j][0]+1)k=0;
        else k=1;
        for(i=1;i<=map[k][j][0];i++){
            if(dis[map[k][j][i]]>dis[j]+len[j]){
                dis[map[k][j][i]]=dis[j]+len[j];
                bef[map[k][j][i]]=j;
            }
        }
    }
    return MAX;
}
 
main(){
    freopen("fence6.in","r",stdin);
    freopen("fence6.out","w",stdout);
    int i,j=MAX,k;
    pre();
    for(i=1;i<=n;i++){
        k=dijkstra(i);
        if(k<j)j=k;
    }
    printf("%d\n",j);
    return 0;
}

Cryptcowgraphy (cryptcow)
又是搜索，這個(gè)就是看了別人的解題報(bào)告。
剪枝方案：
1.如果C O W出現(xiàn)的順序不是C在最前面，W在最后面，剪掉。
2.如果除去C O W后字符串字母和原字符串不符，剪掉。
3.如果 C O W不是成對出現(xiàn)，剪掉
4.用ELFhash函數(shù)為出現(xiàn)的字符串判重。

ELFhash
int hasher(char *k){
 unsigned long h=0,g;
 while(*k){
  h=(h<<4)+*k++;
  g=h &0xf0000000l; //7個(gè)0;
  if(g) h^=g>>24;
  h&=~g;
 }
 return h;
}