POJ1011洛谷4个点TLE

Question

POJ1011问题TLE，求大老回答

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string.h>
using namespace std;

const int maxn=100+10;
int n,mx,sum,nl,k;
int a[maxn],nxt[maxn];
bool vis[maxn];
inline bool cmp(int x1,int y1){
    return x1>y1;
} 
inline bool dfs(int len,int x,int num){
    if(num==k)return true;
    for(int i=x;i<=k;i++){
        if(vis[i]||(i>1&&!vis[i-1]&&!(a[i]^a[i-1])))continue;
        vis[i]=true;
        if(len+a[i]<nl){
            if(dfs(len+a[i],i+1,num+1))return true;
        }
        else if(len+a[i]==nl){
            if(dfs(0,1,num+1))return true;
        }
        vis[i]=false;
        if(len==0)break;
    }
    return false;
}
int main(){
    while(~scanf("%d",&n)){
        if(n==0)break;
        sum=0,mx=0,k=0;
        for(int i=1;i<=n;i++){
            int b;
            scanf("%d",&b);
            if(b>50||b==0)continue;
            a[++k]=b;
            sum+=b;
            mx=max(mx,b);
        }
        //printf("mx %d sum %d\n",mx,sum);
        sort(a+1,a+k+1,cmp);
        /*
        for(int i=1;i<=n;i++)printf("%d ",a[i]);
        printf("\n");
        */
        /*
        memset(nxt,0,sizeof(nxt));
        nxt[k]=k;
        for(int i=k-1;i>=1;i--){
            if(a[i]==a[i+1])nxt[i]=nxt[i+1];
            else nxt[i]=i;
        }
        */
        int ans=0;
        for(int i=mx;i<=(sum>>1)+1;i++){
            if(sum%i!=0)continue;
            nl=i;
            memset(vis,false,sizeof(vis));
            if(dfs(0,1,0)){
                ans=nl;
                break;
            }
        }
        if(ans==0)ans=sum;
        printf("%d\n",ans);
    }
    return 0;
} 

Answer 1

你看一下这个代码行不行

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
 
/**
 * created by 吴家俊 on 2019/9/17.
 */
public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int count = scanner.nextInt();
        ArrayList<Integer> list = new ArrayList();
        int sum;
        while (count != 0) {
            sum = 0;
            for (int i = 0; i < count; i++) {
                int k = scanner.nextInt();
                list.add(k);
                sum += k;
            }
            Bar bar = new Bar(list, sum);
            bar.inputResult();
            count = scanner.nextInt();
            //清空list
            list.clear();
        }
    }
}
 
class Bar {
    private ArrayList<Integer> list;//存储被切后各个棒的长度
    private int[] visit; //访问数组标记某个数是否被使用过 0未使用 1使用
    private int len; //预测最初每个棒的长度
    private int n; //最初棒的个数
    private int sum; //棒的总长度
    private boolean flag; //标记是否得出结果
 
    public Bar(ArrayList<Integer> list, int sum) {
        this.list = list;
        this.sum = sum;
        Collections.sort(list);
        Collections.reverse(list); //按棒长降序排序
    }
 
    private void init() {
        visit = new int[list.size()];
        flag = false;
    }
 
    public void inputResult() {
        for (int i = list.get(0); i <= sum; i++) { //1、缩小len的取值范围
            if (i == sum) {
                System.out.println(i);
            } else if (sum % i == 0) { //2、再次缩小len的取值范围
                n = sum / i;
                len = i;
                init();
                dfs(0, len, 0);
                if (flag) {
                    break;
                }
            }
        }
    }
 
    /**
     * @param index 遍历的起始下标
     * @param l     当前剩余长度 为0时 表示凑成了一个原先的棒
     * @param now   当前已经凑成的棒的根数 为n时 表示得到解
     */
    private void dfs(int index, int l, int now) {
        if (flag) return;
        if (now >= n) {
            flag = true;
            System.out.println(len);
            return;
        }
        for (int i = index; i < visit.length; i++) {
            if (visit[i] == 0 && l - list.get(i) >= 0) {
                visit[i] = 1; //标记已访问
                if (l - list.get(i) == 0) { //凑成了一根棒
                    dfs(0, len, now + 1); //开始寻找下一个棒的起点
                } else {
                    dfs(index + 1, l - list.get(i), now);
                }
                visit[i] = 0; //还原
                if (flag) return;
                if (l == len) return; //3、之前的决策有问题，回退到上一根棒的拼凑过程
                while (i + 1 < visit.length && list.get(i + 1) == list.get(i)) {//4、该点失败后，后面相同的点不用再尝试
                    i++;
                }
            }
        }
    }
}