本文共 1779 字,大约阅读时间需要 5 分钟。
一个整数数组,长度为n,将其分为m份,使各份的和相等,求m的最大值
比如{3,2,4,3,6} 可以分成{3,2,4,3,6} m=1;
{3,6}{2,4,3} m=2
{3,3}{2,4}{6} m=3 所以m的最大值为3
解:poj 1011,搜索+强剪枝
Description
#include#include #include #include #include using namespace std;const int N=64;int stick[N];bool used[N];int num;bool DFS(int unused,int rest,int tgtLen)//要使得组合成stNum组,每个组之和为tgtLen;rest表示第i个组还差rest长度就等于tgtLen{ if(unused ==0 && rest ==0) return true; if(rest ==0)//上一组已经凑够tgtLen,这一组要重新凑tgtLen rest = tgtLen; for (int i = 0;i rest) continue; used[i] = true; if(DFS(unused - 1,rest - stick[i],tgtLen)) return true; used[i] = false;//在这一组还剩余rest的情况下不能满足条件则, if(stick[i]==rest || rest == tgtLen)//如果在一个组刚开始凑的时候,stick[i]放进去,就导致无解,就说明只要有stick[i]在,就不能有解; break; } return false;}int main(){ while (scanf("%d",&num) && num) { memset(used,0,sizeof(used)); int score =0; for(int i=0;i
转载地址:http://xpeti.baihongyu.com/