小猫爬山

发表于 2020-03-24 更新于 2023-09-21 | 字数统计: 209(字) | 阅读时长: 1(分)

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 20;

int n, w, cats[MAXN], f[MAXN], ans;
bool book[MAXN];

void dfs(int ind = 1 /*当前猫的序号*/, int sum = 0 /*当前已用缆车数*/) {
	if(sum > ans) return; //超过当前最大缆车数量，直接退出 
	if(ind == n + 1) { //所有猫全部坐上车，且缆车数量不大于当前最大缆车数量，保存并退出 
		if(sum < ans) ans = sum;
		return; 
	}
	for(int i = 1; i <= sum; i ++) {
		if(cats[ind] + f[i] <= w) {
			f[i] += cats[ind];
			dfs(ind + 1, sum);
			f[i] -= cats[ind];
		}
	}
	f[sum + 1] = cats[ind];
	dfs(ind + 1, sum + 1);
	f[sum + 1] = 0;
}

bool cmp(int x, int y) {
	return x > y;
}

int main() {
	scanf("%d %d ", &n, &w);
	for(int i = 1; i <= n ; i ++) {
		scanf("%d", &cats[i]);
	}
	ans = n;
	sort(cats + 1, cats + 1 + n, cmp);
	dfs();
	printf("%d", ans);
	return 0;
}

O2优化—打开C++所有运行加速开关

发表于 2020-03-20 更新于 2023-09-21 分类于杂项 | 字数统计: 270(字) | 阅读时长: 1(分)

//粘贴复制至头文件下即可
#pragma once 
#pragma GCC diagnostic error "-std=c++11"
#pragma GCC target("avx")
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")