中文题 （一般都比较坑）

思路：DFS



（感谢学长的幻灯片）

这破题把我折腾惨了！！！搞了n天

// by Sirius_Ren

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int n,a[100],sum,jy,maxx,q;

bool vis[100];

bool cmp(int a,int b){return a>b;}

bool dfs(int x,int l,int pos){

    if(x==q)return 1;

    for(int i=pos+1;i<=n;i++){

        if(vis[i]||(!vis[i-1]&&a[i]==a[i-1]&&i>1))continue;

        if(l==a[i]){

            vis[i]=1;

            if(dfs(x+1,jy,0))return 1;

            vis[i]=0;return 0;

        }

        if(l>a[i]){

                vis[i]=1;

                if(dfs(x,l-a[i],i))return 1;

                vis[i]=0;

                if(l==jy)return 0;

            }

        }

    return 0;

}

int main()

{

    while(scanf("%d",&n)&&n){

        maxx=sum=0;

        memset(a,0,sizeof(a));

        for(int i=1;i<=n;i++)scanf("%d",&a[i]),sum+=a[i],maxx=max(maxx,a[i]);

        sort(a+1,a+1+n,cmp);

        for(jy=maxx;jy<=sum;jy++){

            if(sum%jy)continue;

            q=sum/jy;

            memset(vis,0,sizeof(vis));

            if(dfs(0,jy,0)){printf("%d\n",jy);break;}

        }

    }

}

惨痛的失败经历。。。

TLE了一屏半

WA了半屏

在mars_ch&玉环的帮助下终于A了此题。。。

去UVA上交了一遍 1A

还挺快 嘿嘿

和mars_ch争论了很久是if(dfs(x,l-a[i],i))return 1;还是if(dfs(x,l-a[i],pos+1))return 1;

在POJ上都是16msAC的 她表示没有什么区别

但

是

UVA 证明了一切

她的程序got TLE 哈哈哈哈 （青出于蓝而胜于蓝）