POJ 1011--Sticks
に言及
タイトルの大意は、元の数本の長さが同じ棒で切断された長い短い棒がたくさんあって、元の棒の最短の長さを要求しています.
ぶんせき
これは比較的典型的な深さ探索問題であり,従来の棒の長さが最小である可能性が現在の棒の中で最も長い値であるため,まず棒を大きいものから小さいものに並べ替え,max(s 1,s 2,s 3...sn)<=元の長さ<=sum(s 1,s 2,s 3...sn)である.この中で注意したいのは、同じ長さの棒を繰り返し検索しないでください.そうすれば必ずタイムアウトします.ここでは,次の長さの異なる棒の位置を記録した構造体を採用し,探索量を低減した.コードは以下の通り:Memory:232 K Time:32 MS Length:80 LINES
タイトルの大意は、元の数本の長さが同じ棒で切断された長い短い棒がたくさんあって、元の棒の最短の長さを要求しています.
ぶんせき
これは比較的典型的な深さ探索問題であり,従来の棒の長さが最小である可能性が現在の棒の中で最も長い値であるため,まず棒を大きいものから小さいものに並べ替え,max(s 1,s 2,s 3...sn)<=元の長さ<=sum(s 1,s 2,s 3...sn)である.この中で注意したいのは、同じ長さの棒を繰り返し検索しないでください.そうすれば必ずタイムアウトします.ここでは,次の長さの異なる棒の位置を記録した構造体を採用し,探索量を低減した.コードは以下の通り:Memory:232 K Time:32 MS Length:80 LINES
#include
#include
using namespace std;
struct Stick
{
int Length;
bool IsUsed;
int Next;
};
bool Compare(const Stick&s1, const Stick&s2) { return s1.Length > s2.Length; }; //
void Construct(Stick* StickArray, const int& Count) //
{
for (int i = 0; i < Count; ++i)
{
for (int j = i + 1; j < Count; ++j)
{
if (StickArray[i].Length != StickArray[j].Length)
for (; i < j; ++i) StickArray[i].Next = j;
}
StickArray[i].Next = Count;
}
};
int NextNotUsed(const Stick* StickArray, int Current, const int& Count) //
{
while (Current < Count&&StickArray[Current].IsUsed) ++Current;
return Current;
}
int RemSum(const Stick* StickArray, const int& Count, int Start)//
{
int Sum = 0;
for (; Start < Count; Start = NextNotUsed(StickArray, Start + 1, Count))
Sum += StickArray[Start].Length;
return Sum;
}
bool RecurSearch(Stick* StickArray, int Remain, const int& Count, int RemLength, const int& AssumeLength, int FirNotUsed)
{
if (Remain == 0 && RemLength == 0) return true; //
if (RemLength == 0) // ,
{
RemLength = AssumeLength;
FirNotUsed = NextNotUsed(StickArray, 0, Count);
}
for (int i = FirNotUsed; i < Count; i = NextNotUsed(StickArray, StickArray[i].Next, Count))
{
if (RemLength > RemSum(StickArray, Count, i)) return false; //
if (RemLength >= StickArray[i].Length)
{
StickArray[i].IsUsed = true;
if (RecurSearch(StickArray, Remain - 1, Count, RemLength - StickArray[i].Length, AssumeLength, NextNotUsed(StickArray, i, Count))) return true;
StickArray[i].IsUsed = false;
if (RemLength == AssumeLength || RemLength == StickArray[i].Length) return false; // ,
}
}
return false;
};
int Calculate(Stick* StickArray, const int& Count, const int& Sum)
{
int AssumeLength = StickArray[0].Length;
for (; AssumeLength != Sum; ++AssumeLength)
if (Sum%AssumeLength == 0 && RecurSearch(StickArray, Count, Count, AssumeLength, AssumeLength, 0)) break;
return AssumeLength;
};
int main()
{
int Count = 0;
while (cin >> Count&&Count != 0)
{
Stick StickArray[64];
int Sum = 0;
for (int i = 0; i < Count; ++i)
{
cin >> StickArray[i].Length;
Sum += StickArray[i].Length;
StickArray[i].IsUsed = false;
}
stable_sort(StickArray, StickArray + Count, Compare);
Construct(StickArray, Count);
cout << Calculate(StickArray, Count, Sum) << endl;
}
return 0;
}