hello-world

題目分類
Fire Station	圖論，最短路
Soundex	水題
Ferry Loading	DP
Dog & Gopher	水題
Gas Station Numbers	分析，倒推

補(bǔ)充：

Fire Station：
題目給出一些交叉路口，有些路口建有消防站，因此每個路口都有一個離自己最近的消防站，在這些最短的距離中找出最長的！題目要求再建一個消防站（要求編號最小），使這個最長距離最短！考慮到每個路口最多只有二十條邊（題目意思），所以可以用鄰接表存圖然！然后用Dijkstra（或者spfa）算出所有點(diǎn)對之間的最短距離（當(dāng)然Floyd也行，但是可能要慢很多），求出剛開始的最長距離，從小到大枚舉每一個路口，看是否可以減小這個最長距離即可！值得注意的是必需要建一個消防站，因此可以在已經(jīng)建過的路口建!

Ferry Loading：
一看就知道是一道DP題目，開始的時候?qū)嵲诓恢涝趺醋觯髞韰⒖剂艘幌陆獯穑?br>state[i][j]表示前i個汽車能夠讓左邊長度為j的狀態(tài)，那么state[i][j] = true if and on if state[i-1][j-len[k]]=true(0<=k<i) or state[i-1][j]=true;如果前i個汽車的總長度為s，甲板的總長度為Len，那么每個狀態(tài)要滿足 j<=Len,s-j<=Len;
實(shí)現(xiàn)的時候 可以用遞推的方法，那樣更簡單，一旦不能產(chǎn)生新的狀態(tài)就停止！且每個狀態(tài)記錄是由前哪個狀態(tài)變換過來的，輸出的時候可以遞歸輸出答案！
核心代碼(借鑒標(biāo)答)：

void print(int i,int j)
{
    if(i==0)return;
    print(i-1,dp[i][j]);
    printf((j==dp[i][j])?"port\n":"starboard\n");
}

memset(dp,-1,sizeof(dp));
dp[0][0]=0;
for(i=0;i<n;i++)
{
    bool flag=false;
    for(j=0;j<=L;j++)if(dp[i][j]>=0)
    {
        if(j+len[i]<=L&&sum-len[i]-j<=L)
            dp[i+1][j+len[i]]=j,flag=true;
        if(j<=L&&sum-j<=L)
            dp[i+1][j]=j,flag=true;
    }
    if(!flag)break;
}

Gas Station Numbers ：
題目大意是給你 一個數(shù)字N，你可以交換他們每位的數(shù)字 比如 12.5 可以變成 15.2 也可以變成 2.15
你也可以把 2變成 5 ，5變成 2 ，也可以把 6變成 9 ，9 變成 6，對于由 N 所有變換而來的所有可能
，比N大的最小值是多少？

題目要找一個最小的 大于原數(shù)的值，顯然倒序（從低位考慮 ）考慮更方便。
當(dāng)考慮到第 i （0<=i<len）位時，有幾個原則：
1  能在第 i 位上變化獲得答案，就絕不到第 i - 1 位上變動，盡量保持高位不變
2  若在第 i 位上有多種變化可能，選擇最小的值去替換第 i 位
3  如果在第 i 位上發(fā)生變化，則有可行解，如果一直倒推到第 0 位還不能替換，則無解
4  第 i 位替換好了的話， i+1位 到 len - 1位（即之后的數(shù)）要求最小
所以在倒推的時候，可以開一個數(shù)組visit[10]記錄當(dāng)前可以用來替換的資源，時間復(fù)雜度只是用在排序上，為nlog(n)