为啥这个会超时呢,是数据加强了吗
查看原帖
为啥这个会超时呢,是数据加强了吗
579961
JunBuJian楼主2022/3/16 23:01
#include<iostream>

using namespace std;
const int N = 25;
int s[N],t[N],ans,sum,x1,x2,mdeep;

void dfs(int u)
{
    //边界
    if(u > mdeep)
    {
        x1 = max(x1,x2);
        return ;
    }
    
    
    for(int i = 1;i <= mdeep;i ++)
    {
        //选
        if(x2 + t[i] <= sum/2)
        {
            x2 += t[i];
            dfs(u + 1);
            x2 -= t[i];
        }
        //不选
        dfs(u + 1);
    }
    
}

int main()
{
    for(int i = 1;i <= 4;i ++) cin >> s[i];//读入习题数量
    
    for(int i = 1;i <= 4;i ++)
    {
        sum = 0,mdeep = s[i];
        for(int i = 1;i <= mdeep;i ++)
            {
                cin >> t[i];
                sum += t[i];
            }
        x1 = 0,x2 = 0;
        
        dfs(1);
       
        ans += (sum - x1);
       
    }
    
    cout << ans;
    return 0;
}
2022/3/16 23:01
加载中...