[zoj3623]背包模型
2024-09-07 14:10:43
给定n种物品,每种物品需要ti时间生产出来,生产出来以后,每单位时间可以创造wi个价值。如果需要创造至少W个价值,求最少时间。
思路:dp[j]表示用时间j所能创造的最大价值,则有转移方程:dp[j + t[i]] = max(dp[j + t[i], dp[j] + t * w[i]])。另外是否需要按一定顺序排序呢??以下是ac代码。
#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 rep1(a, b) for (int a = 1; 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 f[], a[], b[]; int main() {
//freopen("in.txt", "r", stdin);
int n, l;
while (cin >> n >> l) {
rep(i, n) {
sd(a[i]);
sd(b[i]);
}
int maxt = ;
mem0(f);
rep(i, n) {
rep(j, maxt) {
f[j + a[i]] = max(f[j + a[i]], f[j] + j * b[i]);
}
}
int ans;
rep(i, maxt * ) {
if (f[i] >= l) {
ans = i;
break;
}
}
cout << ans << endl;
}
return ;
}
最新文章
- AT常见问题
- 从一个故障说说Java的三个BlockingQueue
- Kosaraju 算法
- JS的Touch事件们,触屏时的js事件
- Python 之range 和 xrange
- (五)uboot移植补基础之shell
- 微软Azure的多媒体编码服务示例
- QQwry
- iOS项目开发常用功能静态库
- jsp数据
- 基于JDK动态代理和CGLIB动态代理的实现Spring注解管理事务(@Trasactional)到底有什么区别。
- 【redis 基础学习】(六)Redis HyperLogLog
- SQL Server 数据库部分常用语句小结(三)
- ROS笔记 Topics
- 【读书笔记】iOS-属性
- poj 3207(2-SAT+SCC)
- Kafka:ZK+Kafka+Spark Streaming集群环境搭建(二十九):推送avro格式数据到topic,并使用spark structured streaming接收topic解析avro数据
- 弄懂linux shell对包含$的变量的执行过程?
- H264编码 封装成MP4格式 视频流 RTP封包
- redmine安装-BitNami 提供的一键安装程序