hdoj 1016 Prime Ring Problem深検索トレース
1200 ワード
非常に入門した深く追究して問題を追究する.http://acm.hdu.edu.cn/showproblem.php?pid=1016
剪定を最適化していません.実行時間は長いですが、acはできます.
剪定を最適化していません.実行時間は長いですが、acはできます.
#include
#include
using namespace std;
int n,id=0; //n ,id case
int depth = 0; // ,
int solution[21]; // , 1 , 1 , 0
int used[21]; // , 1 n n
//
bool isPrime(int num)
{
for(int i=2 ; i<=sqrt(num) ; ++i)
{
if(num % i == 0)
{
return false;
}
}
return true;
}
// , 2 n
void PrimeRing(int curr )
{
if(depth == n-1 && isPrime(curr+1)) // , n-1 (1 ) 1
{
cout << "1"; // 1 ,1
for(int i=0 ; i> n)
{
for(int i=0 ; i<=n ; ++i) //
used[i] = 0;
used[1] = 1; // 1 ,1
cout << "Case " << ++id << ":" << endl;
PrimeRing(1);
cout << endl;
}
return 0;
}