Sticks(UVA - 307)
題目鏈接
演算法
DFS+剪枝
1.這道題題意就是說原本有一些等長的木棍，后來把它們切割，切割成一個個最長為50單位長度的小木棍，現在想讓你把它們組合成一個個等長的大木棍，要求這個拼接成的大木棍的長度最小，問最小長度是多少，(注意，在接下來的介紹中，將最后的大木棍表述為拼接木棍，小木棍還是叫小木棍)
2.看完這個題，基本思路是從一個小木棍開始找，找到一個未使用的小木棍后拼接，當拼接成的長度是所有小木棍長度和的約數時，就暫時把它定義為拼接木棍的最小長度，然后計算最后需拼接成多少個這個長度的拼接木棍，然后繼續尋找，達到這個長度后累加，如果實在沒有，重新定義拼接木棍的最下長度，
如果按部就班的按照上面的基本思路做肯定會超時的，而且涉及的點比較多，因為當你所找到的那個最小長度不能夠讓所有小木棍都能拼接成時，還需繼續尋找，這樣過于復雜，
那么換個思路，既然是拼接木棍，那么最終拼接木棍的最小長度一定大于等于所有小木棍的最大長度，
那么我們就可以從小木棍的最大長度這個地方開始列舉拼接木棍的長度，這是其中一個可以優化的地方，那什么時候到頭呢，拼接木棍的長度最大可以列舉到所有小木棍的長度和，然后就不能再大了，考慮到拼接木棍的長度是小木棍長度和的約數，那么就可以列舉到長度和/2，因為大于長度和/2的部分就沒有長度和的約數了(除了長度和本身)，這樣可以節省一定的時間，當滿足條件時，直接退出回圈，輸出即可，如果回圈了所有約數都不滿足，直接輸出長度和即可，
下面介紹幾個剪枝的地方：
- 將存盤小木棍長度的陣列從大到小排序，這樣做的原因是長度大的小木棍相對于長度小的小木棍一定有相對較小的選擇，這樣在一定情況下節省了時間，
- 列舉拼接木棍的長度時，只考慮約數(小木棍長度和的約數)，其余的無需考慮，
- 如果當前木棍與前一個木棍長度相同，并且前一個木棍拼接失敗，那么直接跳過當前木棍即可，
- 當目前拼接長度為0時，但嘗試了所有的木棍都沒有拼接成功，則證明這個拼接木棍的長度無法拼成，return false即可，
3.這道題是一道典型的DFS剪枝題目，涉及的剪枝比較多，稍有一點沒涉及到就會TLE，
C++ 代碼
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1000;
int n, units[N];
int sum_length; /*所有小木棍的總長度*/
bool st[N]; /*標記當前小木棍是否被使用*/
int res; /*拼接長度*/
int cnt; /*在拼接長度為res時最終能形成的拼接木棍的個數*/
bool dfs(int len, int k, int i) /*len表示當前的拼接長度,k表示滿足res的拼接木棍的個數,i表示下標為i的這個木棍已經考慮完,再列舉時從下一個木棍開始列舉即可*/
{
if(len == res)
{
k++; /*達到拼接長度時,累加拼接木棍的個數*/
len = i = 0;
}
if(k == cnt) return true;
for(int j = i + 1; j < n; j++)
{
if(st[j]) continue; /*當前木棍已經被使用,則不能再使用*/
if(units[j] == units[j-1] && !st[j-1]) continue; /*前一個木棍與它長度相同,但沒被使用,那該木棍也無需再驗證是否需要使用了*/
if(units[j] + len > res) continue; /*大于拼接長度,則不能考慮*/
st[j] = true;
if(dfs(len + units[j], k, j))
return true;
st[j] = false;
if(len == 0)
return false;
}
return false;
}
int main()
{
while(cin >> n && n)
{
sum_length = 0;
for(int i = 0; i < n; i++)
{
cin >> units[i];
sum_length += units[i];
}
sort(units, units + n, greater<int>());
for(res = units[0]; res <= sum_length / 2; res ++)
{
memset(st, 0, sizeof st);
if(sum_length % res != 0) continue;
cnt = sum_length / res; /*預測的初始木棒個數*/
st[0] = true; /*標記第一個最長的小木棍被使用*/
if(dfs(units[0], 0, 0))
{
cout << res << endl;
break;
}
}
if(res > sum_length / 2) /*大于它時,說明沒有可形成的長度,直接輸出長度和即可*/
cout << sum_length << endl;
}
}
思路來源
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/165399.html
標籤：其他
上一篇：模板——差分約束