Java Out Of Memory 方法 mysql安装 Jetson Nano matplotlib flask browser layer jScrollPane vue遍历 jq获取元素 oracle删除表字段 mysql查看锁表 idea整理代码格式 ab软启动器 websocket库 Navicat python取随机数 python正则表达 javaswitch语句 java运算符 java集合框架图 java集合类型 java配置jdk php项目实例 java游戏制作 图吧导航怎么样 xp画图工具 神龙激活 pdf安装包官方下载 掌门一对一下载 英雄联盟设置 还原软件哪个好 流媒体下载 中文微信小程序API 固态硬盘有什么用 苹果电脑怎么收藏网页 ae添加关键帧 excel指数函数 3dmax2009注册机
当前位置: 首页 > 学习教程  > 编程语言

搞不懂的暴搜

2020/7/24 10:51:53 文章标签:

暴搜优化.
分析
令第 i 种装备的数量为sum[i],显然如果 sum[i]不为 0 那么这种装备必选一件,在这时需要考虑的总方案数为 ∏
max(sum[i], 1),其中 ∑sum[i] ≤ 50。最坏情况下所有
sum 的值都相同,令它们都等于 k,则方案数为 kn/k ,当 k 取 3 时取到最大值 3n/3 ,在 n = 50 时
并不算太大,因此可以直接爆搜所有方案得到最优解。
需要注意的是,sum[i] = 0 的部分应该直接跳过,以保证搜索树上每一层的节点数至少是上一层的两倍,使得时间复杂度为 O(3n/3 ),否则会退化成 O(n*3n/3) 而 TLE。

#include <bits/stdc++.h>
#define ll long long
#define T int t;scanf("%d", &t);while(t--)
using namespace std;
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
const ll mod = 1e9+7;
const int maxn = 2e5+5;
ll ans = 0;
int n,m;
int f[55][55][5];
int nxt[55];
int sum[55];
void dfs(int k, int a, int b, int c, int d){
    if(k > m){
        ll cnt = 1ll * a * b * c * d;
        ans = max(cnt,ans);
        return;
    }
    int num = sum[k];
    //如果当前种装备数量为0,直接搜下一种数量不为0的装备种类
    if(num == 0){		
        dfs(nxt[k],a,b,c,d);
        return;
    }
    for(int i = 1; i <= num; i ++){
        dfs(k + 1, a + f[k][i][1], b + f[k][i][2], c + f[k][i][3], d + f[k][i][4]);
    }
}
int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        scanf("%d %d", &n, &m);
        int k; 
        memset(sum,0,sizeof(sum));
        while(n--){
            scanf("%d", &k);
            sum[k]++;		//第k种装备的数量
            for(int i = 1; i <= 4; i++)
                scanf("%d", &f[k][sum[k]][i]);	//四种属性值
        }
        k = m + 1;
        //核心代码,记录下一种数量不为0的装备是哪种
        for(int i = m; i > 0; i --){
            nxt[i] = k;
            if(sum[i]) k = i;
        }
        ans = 0;
        dfs(1,100,100,100,100);
        printf("%lld\n", ans);
    }
 
    return 0;
}

本文链接: http://www.dtmao.cc/news_show_50348.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?