harry12800

常用链接

统计

最新评论

2011年9月8日 #

PKU 1011 Sticks &&hdu 1455 sticks

#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
//三个剪枝
int a[105],v,n;
bool flag,us[105];

void DFS(int w,int sum)
{
     if(sum == 0)flag= false;//找到；
     else
     for(int i =0 ;i < n&&flag;i++)
     {
           if(!us[i]&&w-a[i]>=0)
           {
              us[i] = true;//搜索的标记
              if(w-a[i]==0)
              DFS(v,sum-a[i]);
              else
              DFS(w-a[i],sum-a[i]);
              us[i]= false;
              if(w == a[i])return ;//这个意思是如果剩余的要求的长度和目前的相同；已经做过了不行的话，意味这v是不符合的，不做了
              if(w == v && a[i] < v)return ;//这个意思是如果剩下的长度刚从v开始时，然而a[i]却比v小不行的话，那也是不行的，对不对？
              while(a[i]==a[i+1])i++;//这个意思是如果a[i]长度的不符合，那这个长度的都没必要再做了
           }
     }
}

bool cmp(const int &a,const int &b){return a>b;}//排序规则；
int main()
{
    int sum,i;
    while(scanf("%d",&n)&&n)
    {
          flag = true;
          sum =0;               
          for(i =0 ;i <n ;i++)
          {
                scanf("%d",&a[i]);
                sum+=a[i];//所有棍子总和长度
          }
          sort(a,a+n,cmp);//大到小排序   如果这里不从大到小排序也会Time Limit Exceeded
          for(v = a[0] ; v <= sum;v++)// 从最长的长度开始找
          if(sum%v==0)//能分成 sum/v 份，每份分成v的长度
          {
                  if(sum==v)printf("%d\n",sum);
                  else
                  {
                      memset(us,false,sizeof(us));
                      DFS(v,sum);//深度搜索v长度的是否符合
                      if(!flag)
                      {
                               printf("%d\n",v);
                               break;//找到就退出
                      }
                  }
          }
    }
    return 0;
}

posted @ 2011-09-08 20:02 周国柱 阅读(188) | 评论 (0) | 编辑 收藏

仅列出标题