为什么0 QWQ
  • 板块P1120 小木棍
  • 楼主__Cielo__
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/7/23 09:31
  • 上次更新2024/7/23 10:23:50
查看原帖
为什么0 QWQ
1110182
__Cielo__楼主2024/7/23 09:31

我的代码和题解有啥区别吗?

为啥他的能过我的不能QWQ

My Code

#include<iostream>
#include<stdlib.h>
#define N 70
using namespace std;
int maxn,minn;
int arr[N];
void dfs(int I,int sum,int h,int p)
{
	if(I==0)
	{
		cout<<h;
		exit(0);
	}
	if(sum==h)
	{
		dfs(I-1,0,h,maxn);
		return;
	}
	for(int i=p;i>=minn;i--)
	{
		if(arr[i]&&i+sum<=h)
		{
			arr[i]--;
			dfs(I,sum+i,h,i);
			arr[i]++;
			if(sum==0||sum+i==h)
				break;
		}
	}
	return;
}
int main()
{
	int n,t,num;
	cin>>n;
	minn=N;
	while(n--)
	{
		cin>>t;
		if(t<=50)
		{
			arr[t]++;
			num+=t;
			maxn=max(maxn,t);
			minn=min(minn,t);
		}
	}
	t=num>>1;
	for(int i=maxn;i<=t;i++)
	{
		if(num%i==0)
		{
			dfs(num/i,0,i,maxn);
		}
	}
	cout<<num;
	return 0;
}

The AC Code

#include<cstdio>
#include<cstdlib>
const int N = 70 ;
int n , cnt , tot , maxn , minn , tm[ N ] /* 2 */ ; 
void dfs( int res , int sum , int target , int p ) {
    if( res == 0 ) {
        printf("%d", target  );
        exit( 0 );
    }
    if( sum == target ) {
        dfs( res - 1 , 0 , target , maxn );
        return;
    }
    for( int i = p ; i >= minn ; i -- ) { // 2  3 
        if( tm[ i ] && i + sum <= target ) {
            tm[ i ] -- ;
            dfs( res , sum + i , target , i );
            tm[ i ] ++ ;
            if ( sum == 0 || sum + i == target )  //4
                break;
        }
    }
    return;
}
int main() {
    scanf("%d" , &n ) ;
    minn = N ;
    int temp;
    while( n -- ) {
        scanf("%d" , &temp );
        if( temp <= 50 ) {
            cnt ++;
            tm[ temp ] ++;
            tot += temp;
            maxn = maxn > temp ? maxn : temp ;   //1
            minn = minn < temp ? minn : temp ;
        }
    }
    temp = tot >> 1;
    for( int i = maxn ; i <= temp ; i ++ ) {
        if( tot % i == 0 ) {
            dfs( tot / i , 0 , i , maxn );
        }
    }
    printf("%d" , tot );
    return 0;
}
2024/7/23 09:31
加载中...