}
cout << endl;
return;
}
if( total > Target )
return;
for( int i=index; i<4; i++)
{
total += coin[i];
solution.push_back( coin[i] );
dfs(i);
solution.pop_back();
total -=coin[i];
}
}
int _tmain(int argc, _TCHAR* argv[])
{
while(1)
{
count=0;
cin >> Target;
dfs(0);
cout << count <
}
return 0;
}
2，马戏团里有个叠罗汉的表演，为了便于美观，下面的人身高和体重都要大于上面的人。现在知道n个演员的身高和体重，请问最多能叠多少层?
解答：
思路：
首先生成一个有向图，用连接矩阵的方式来表示。
map[i][j]==1表示第i个人上面可以放第j个人。
然后开始对每个人进行深度搜索，这个图中不可能有环。
所以对于每个人来说就是一棵树，搜索树的高度。
再找出最高的高度即是答案。
[cpp] view plaincopyprint?
#include "stdafx.h"
#include
#include
#include
#include
using namespace std;
int N=0;
double *weight;
double *height;
int **map;
int maxDepth=0;
vector bestPath;
int dfs( int index, vector &path )
{
int flag=0;
int depth = 0;
vector bestPath;
for( int i=0; i
{
if( map[index][i] != 0)
{
flag = 1;
vector tPath;
int t = dfs(i, tPath);
if( t > depth )
{
path = tPath;
depth = t;
}
}
}
if( flag==0 )
{
path.clear();
path.push_back(index);
return 1;
}
else
{
// path = bestPath;
path.push_back(index);
return depth+1;
}
}
void CreateMap()
{
map = new int*[N];
for( int i=0; i
{
map[i] = new int [N];
memset( map[i], 0, N*sizeof(int) );
}
for( int i=0; i
{
for( int j=0; j
{
if( weight[j]
map[i][j]=1;
}
}
}
void CreateData()
{
ofstream out( "in.txt" );
int N = 30;
out << N <
for( int i=0; i
out << rand() << " ";
out << endl;
for( int i=0; i
out << rand() << " ";
}
int main()
{
CreateData();
freopen( "in.txt", "r", stdin );
cout << "Please input N:" <
cin >> N;
height = new double[N];
weight = new double[N];
for( int i=0; i
cin >> height[i];
for( int i=0; i
cin >> weight[i];
CreateMap();
int depth=0;
for(int i=0; i
{
vector tPath;
int t=dfs(i,tPath);
if( t>depth )
{
bestPath = tPath;
depth = t;
}
}
cout << depth <
for( int i=0; i<(int)bestPath.size(); i++)
{
cout << height[bestPath[i]]<< " " << weight[bestPath[i]]<
}
return 0;
}