强烈建议加强数据,dfs无剪枝2^nAC
查看原帖
强烈建议加强数据,dfs无剪枝2^nAC
1074084
asd890123楼主2024/6/9 11:15

2^100次方约1e30,不吸氧最长37ms(#7),总时长206ms,吸氧最长22ms,总时长150ms。

#include <iostream>

struct{int a,b,c;}a[105];
int n,m,X,ans = -0x80000000;

void dfs(int x,int data,int ability,int cost){
    
    if (ability > m || cost > X) return;
    ans = std::max(ans,data);
    if (x > n) return;
    dfs(x + 1,data,ability,cost);
    dfs(x + 1,data + a[x].a,ability + a[x].b,cost + a[x].c);
    
}//正在考虑是否选择第x个人,当前选择的人可获得的资料数量为data,伪装能力为ability,需要的工资为cost

int main(){
    
    std::ios::sync_with_stdio(0);
    std::cin.tie(0),std::cout.tie(0);
    
    std::cin >> n >> m >> X;
    for (int i = 1;i <= n;i++) std::cin >> a[i].a >> a[i].b >> a[i].c;
    dfs(1,0,0,0);
    std::cout << ans << '\n';
    
    return 0;
}
2024/6/9 11:15
加载中...