[hdu3631]背包或中途相遇法
2024-09-07 14:21:37
暴力的背包:
#pragma comment(linker, "/STACK:10240000,10240000") #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <map>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <ctime>
#include <cctype>
#include <set> using namespace std; #define mem0(a) memset(a, 0, sizeof(a))
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define define_m int m = (l + r) >> 1
#define rep(a, b) for(int a = 0; a < b; a++)
#define all(a) (a).begin(), (a).end()
#define lowbit(x) ((x) & (-(x)))
#define constructInt4(name, a, b, c, d) name(int a = 0, int b = 0, int c = 0, int d = 0): a(a), b(b), c(c), d(d) {}
#define constructInt3(name, a, b, c) name(int a = 0, int b = 0, int c = 0): a(a), b(b), c(c) {}
#define constructInt2(name, a, b) name(int a = 0, int b = 0): a(a), b(b) {}
#define pc(a) putchar(a)
#define ps(a) printf("%s", a)
#define pd(a) printf("%d", a)
#define sd(a) scanf("%d", &a) typedef double db;
typedef long long LL;
typedef pair<int, int> pii;
typedef multiset<int> msi;
typedef set<int> si;
typedef vector<int> vi;
typedef map<int, int> mii; const int dx[] = {, , , -, , , -, -};
const int dy[] = {, , -, , -, , , -};
const int maxn = 1e5 + ;
const int maxm = 1e5 + ;
const int maxv = 1e7 + ;
const int max_val = 1e6 + ;
const int MD = 1e9 +;
const int INF = 1e9 + ;
const double PI = acos(-1.0);
const double eps = 1e-; template<class T> T gcd(T a, T b) { return b == ? a : gcd(b, a % b); } int t, sum[], a[];
bool f[];
int main() {
//freopen("in.txt", "r", stdin);
int n;
while (cin >> n >> t) {
rep(i, n) sd(a[i]);
sort(a, a + n);
sum[] = a[];
rep(i, n - ) sum[i + ] = sum[i] + a[i + ];
mem0(f);
f[] = true;
rep(i, n) {
int maxt = min(t, sum[i]);
for (int j = maxt; j >= a[i]; j--) {
f[j] = f[j] || f[j - a[i]];
}
}
int ans;
for (int i = t; i >= ; i--) {
if (f[i]) {
ans = i;
break;
}
}
cout << ans << endl;
}
return ;
}
最新文章
- C++ STL之vector用法总结
- Oracle逻辑备份与恢复
- 简单说一个IOCP不好的地方
- EventKit 学习(译)
- 基于tiny4412的Linux内核移植 --- aliases节点解析
- 微课程--Android--Android概述
- ros使用RPLIDAR激光雷达
- tomcat的OutOfMemoryError(PermGen space)解决方法
- js 正则 数值验证
- hdu1026 Ignatius and the Princess I (优先队列 BFS)
- Hacker(九)----黑客攻防前准备1
- 《Python编程从入门到实践》_第六章_字典
- oracle如何连接别人的数据库,需要在本地添加一些配置
- 解决Windows和Linux使用npm打包js和css文件不同的问题
- pinyin utils
- MySQL Workbench 创建数据库,添加新表,添加字段
- [蛙蛙推荐]SICP第一章学习笔记-编程入门
- 2019 校内赛 RPG的天赋分支(贪心)
- 编译NDK的source code一定要用release mode!
- DELL MD3200i存储控制器解锁方法