杭电--1258 深度搜索（sum it up）

DFS还是不太懂，递归是个硬伤啊。。。。

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1258

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cstdio>
using namespace std;
vector<int> digits(13);
//出现的数字
vector<int> digits_num(13);
//对应的个数
int m = 0;
//digits中具体有m个数
vector<int> f(13);
//遍历搜索时候取得digits的数目
bool out = false;
//如果out是true说明有输出项
int sum;
void DFS(int start);
int main()
{
int n;
while(cin >> sum >> n)
{
out = false;
m = 0;
if(sum ==0 && n==0)
break;
//输入值，并初始化digits和digits_num数组
for(int i=0; i<n; i++)
{
if(i == 0)
{
cin >> digits[m];
digits_num[m] = 1;
m++;
}
else
{
int k;
cin >> k;
if(k == digits[m-1])
{
digits_num[m-1]++;
}
else
{
digits[m] = k;
digits_num[m] = 1;
m++;
}
}
}
//
测试，输出digits和digits_num数组
//
copy(digits.begin(), digits.end(), ostream_iterator<int>(cout, "t"));
//
cout << endl;
//
copy(digits_num.begin(), digits_num.end(), ostream_iterator<int>(cout, "t"));
//
深度搜索
cout << "Sums of " << sum << ":" << endl;
DFS(0);
if(out == false)
cout << "NONE" << endl;
}
return 0;
}
void DFS(int start)
{
int tot = 0;
//
cout << "s=" << s << endl;
//
cout << "m=" << m << endl;
//计算和tot
//
cout << "start:" << endl;
for(int i=0; i<m; i++)
{
if(f[i] != 0)
tot = tot + digits[i] * f[i];
//
cout << "f[" << i << "]=" << f[i] << endl;
}
//
cout << "tot=" << tot << endl;
//
cout << "end:" << endl << endl;
//
getchar();
//
getchar();
//剪枝
if(tot > sum)
return;
//打印结果
if(tot == sum)
{
int flag = true;
for(int i=0; i<m; i++)
{
if(f[i] != 0 && flag)
{
flag = false;
for(int j=0; j<f[i]; j++)
{
if(j == 0)
cout << digits[i];
else
cout << "+" << digits[i];
}
}
else
{
if(f[i] != 0)
{
for(int j=0; j<f[i]; j++)
cout << "+" << digits[i];
}
}
}
cout << endl;
out = true;
return ;
}
for(int i=start; i<m; i++)
{
for(int j=digits_num[i]; j>0; j--)
{
f[i] = j;
DFS(i+1);
}
f[i] = 0;
}
}
/*
4 6 4 3 2 2 1 1
*/

最后

以上就是光亮水蜜桃为你收集整理的杭电--1258 深度搜索（sum it up）的全部内容，希望文章能够帮你解决杭电--1258 深度搜索（sum it up）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。