【CF500F】New Year Shopping

题目

题目链接:https://codeforces.com/contest/500/problem/F
(n) 种商品,第 (i) 种商品的价格是 (c_i) ,购买后可以增加 (h_i) 的快乐指数,将于第 (t_i) 天上市。商品的保质期为 (p) 天,过期后不能再购买,即第 (i) 种商品只能在第 (t_i) 天到第 (t_i+p-1) 天之间购买,每种商品只能购买一次。
(q) 个询问,每次给定两个整数 (a,b) ,求在第 (a) 天去购物,最多使用 (b) 元的情况下可以得到的最大快乐指数。询问之间互不干扰。
(nleq 3times 10^4)(qleq 2times 10^4),所有价格 (leq 3times 10^4),所有时间和快乐指数 (leq 2times 10^4)

思路

这道题似乎有很多做法,但是我只能想到卑微的 (O(nqlog n))
因为所有物品持续的时间都是一样的,所以按照上架时间排序后,每次的询问就是把一段区间的物品拿出来做 01 背包。
也就是需要维护一个队列,然后在某一时刻查询队列内所有物品的 01 背包。
而一个队列可以用两个栈 (s1,s2) 来实现:插入物品就往 (s2) 插入;删除物品就在 (s1) 删除;当 (s1) 为空时,就把 (s2) 所有元素依次弹出插入 (s1)
然后维护两个栈中每一个元素到栈底的背包。按照时间离线询问,然后只需要合并一下两个栈栈顶的背包即可。
时间复杂度 (O(nq))
实现上不需要真的开栈,维护区间 ([l,mid]) 为第一个栈的元素,([mid+1,r]) 为第二个栈的元素即可。

代码

#include <bits/stdc++.h> using namespace std;  const int N=4010,M=20010; int n,p,Q,l,r,mid,f[N][N],ans[M];  struct node1 { 	int w,v,t; }a[N];  struct node2 { 	int m,t,id; }b[M];  bool cmp1(node1 x,node1 y) { 	return x.t<y.t; }  bool cmp2(node2 x,node2 y) { 	return x.t<y.t; }  void insert(int x,int *g,int *h) { 	memcpy(g,h,sizeof(f[0])); 	for (int i=4000;i>=a[x].w;i--) 		g[i]=max(g[i],g[i-a[x].w]+a[x].v); }  int main() { 	scanf("%d%d",&n,&p); 	for (int i=1;i<=n;i++) 		scanf("%d%d%d",&a[i].w,&a[i].v,&a[i].t); 	scanf("%d",&Q); 	for (int i=1;i<=Q;i++) 	{ 		scanf("%d%d",&b[i].t,&b[i].m); 		b[i].id=i; 	} 	sort(a+1,a+1+n,cmp1); 	sort(b+1,b+1+Q,cmp2); 	l=1; mid=r=0; 	for (int t=1,i=1;t<=20000;t++) 	{ 		for (;r<n && a[r+1].t==t;r++) 			insert(r+1,f[r+1],f[(r==mid)?0:r]); 		while (l<=mid && a[l].t+p==t) l++; 		if (l>mid) 		{ 			mid=r; 			for (int j=mid;j>=l;j--) 				insert(j,f[j],f[(j==mid)?0:j+1]); 		} 		for (;i<=Q && b[i].t==t;i++) 			for (int j=0;j<=b[i].m;j++) 			{ 				int res1=(l<=mid) ? f[l][j] : 0; 				int res2=(mid<r) ? f[r][b[i].m-j] : 0; 				ans[b[i].id]=max(ans[b[i].id],res1+res2); 			} 	} 	for (int i=1;i<=Q;i++) 		printf("%dn",ans[i]); 	return 0; } 

推荐这些文章:

Codeforces 620E - New Year Tree

dfs序 + 状态压缩 + 线段树
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 4e5 + 10, M = N * 2;
int n, m;
int w[N], h[N], e[M], ne[M], idx;
int id[N], nw[N], sz[N], cnt;
struct Node {
int l, r;
LL tag, state;
}tr[N * 4];
void add(int a, int b)
{
e[idx] = b,...

【每日一题】【直接循环&二分查找】2022年2月10日-NC32 求平方根

描述实现函数 int sqrt(int x).计算并返回 x 的平方根(向下取整)

 
方法1:直接循环

import java.util.*;

public class Solution {
/**
*
* @param x int整型
* @return int整型
*/
public int sqrt (int x) {
for (int i = 1; i <= x; i++) {
if(i * i == x) {
return i...

写一个判断素数的函数,在主函数输入一个整数,输出是否是素数的消息。

#include<stdio.h>int test(int x){ int i=1; for(i=1;i<x;i++){ if(x%i==0&&x>2) return 0; else return 1; }
}int main(){ int test(int x); int b; printf("输入整数:\n"); scanf("%d",&b); if(test(b)==0) printf("非素数"); else printf("素数")...

实验8-1-1 利用指针找最大值 (10 分)

#include <stdio.h>

void findmax(int *px, int *py, int *pmax);

int main()
{
int max, x, y;

scanf("%d %d", &x, &y);
findmax(&x, &y, &max);
printf("%d\n", max);

system("pause");
return 0;
}

/* 你的代码将被嵌在这里 */
void findmax(int *px, int *py, int *pma...

1006 换个格式输出整数

#include<stdio.h>
int main(){
int n;
char a[100]={0};
scanf("%d",&n);
int b=n/100;
for(int i=0;i<b;i++){
a[i]='B';
}
int s=n/10%10;
for(int i=b;i<s+b;i++){
a[i]='S';
}
int x=n%100%10;
int j=1;
for(int i=b+s;i<s+b+x;...

基础算法 143.最大异或对

此题目使用Trie树,代码中的N代表着节点可能的最大个数。

#include<iostream>
using namespace std;

const int N = 3100010;
int son[N][2], num[100010], idx;

void insert(int k){
scanf("%d", &num[k]);
int i = 30;
int p = 0;
while(i+1){
int u = (num[k] >> i) & 1;
if(!son[p][u]...

1109. 航班预订统计

这里有 n 个航班,它们分别从 1 到 n 进行编号。
有一份航班预订表 bookings ,表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti (包含 firsti 和 lasti )的 每个航班 上预订了 seatsi 个座位。
请你返回一个长度为 n 的数组 answer,里面的元素是每个航班预定的座位总数。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/pr...

BZOJ#1491[NOI2007]社交网络

[NOI2007]社交网络

思路:
使用floyd算法并记录路径,
代码:
const int N = 110;
int g[N][N];
int d[N][N];
double ans[N];
void solve(int Case) {
int n, m;
scanf("%lld%lld", &n, &m);
memset(g, 0x3f, sizeof g);
for (; m--;) {
int a, b, w;
scanf("%lld%lld%lld", &a, &b, &w)...

CodeForces 1619D New Year's Problem

New Year's Problem
有n个人,m个商店,每个商店有n个物品,也有对应的\(a_i\),代表第i个人对这个物品的好感度。现在要求进入n-1个商店,为每个人购买一件物品,使得最后n个人中,获得物品的最低好感度最高
二分
一开始以为是贪心或者排序,没往二分上面想,想了半天的暴力也没想到有什么办法能够找到n-1家商店的情况
后来有人说是二分的时候,也没有什么头绪,因为不知道如何去检查一个答案是否正确
这里给出二分能够完成的原因:假设现在的值是X,当X大于最后的答案的时候,必然是不成立的;当X小于最后答案的时候,是可以成立的,因此他是一个单调的函数,可以使用二分来查找答案
如何检查答...

二分模板

#include<iostream> using namespace std; const int N=100010; int n,m; int q[N]; int main(){ scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%d",&q[i]); while(m--){ int x; scanf("%d",&x); int l=0,r=n-1; while(l<r){ ...

文章标题:【CF500F】New Year Shopping
文章链接:https://www.dianjilingqu.com/2876.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>