codeforces 500F New Year Shopping(dp)

$link$:添加链接描述

显然考的是0/1背包
重复运算很浪费时间 就可以考虑分组去优化运算

为了方便说明/分组 我们把持续时间移到我们访问的时间 也就是一个物品变成一个时间点 把我们去的时间变成一段

那么本来 t i t_i ti​ 时刻去 会转化成 [ t i − p + 1 , t i ] [t_i-p+1,t_i] [ti​−p+1,ti​]

我们考虑如何分组减少背包的次数

很显然我们先对物品和时间都进行排序

那么我们取 $T=1,p+1,2p+1....$ 那么所有的区间都会被覆盖一次，我们只要以 $T$ 为中轴 所有$dp$ 计算时合并即可

边界细节挺多的。。

#include 
using namespace std;
#define rep(i,j,k) for(int i = j;i <= k;++i)
#define repp(i,j,k) for(int i = j;i >= k;--i)
#define fr first
#define se second
int rd() {int sum = 0;char c = getchar();bool flag = true;while(c < '0' || c > '9') {if(c == '-') flag = false;c = getchar();}while(c >= '0' && c <= '9') sum = sum * 10 + c - 48,c = getchar();	if(flag) return sum;else return -sum;
}
struct item {int c,v,t;
}a[4010];
struct host {int t,c,id;
}b[20100];
int n,p,q;
bool cmp1(item a,item b) {return a.t < b.t;}
bool cmp2(host a,host b) {return a.t < b.t;}
void init() {n = rd();p = rd();rep(i,1,n) a[i].c = rd() , a[i].v = rd() , a[i].t = rd();q = rd();rep(i,1,q) b[i].t = rd() , b[i].c = rd() , b[i].id = i;sort(a+1,a+n+1,cmp1);sort(b+1,b+q+1,cmp2);return;
}
//???ost??说  ????[t-p+1,t];
int dp[2][4050][4050];
int ans[20100];
void merge(int A,int B,int C,int D,int xxx,int yyy) {int l = A,r = C-1;rep(i,xxx,yyy) { int L = b[i].t-p+1,R = b[i].t;while(a[l].t < L && l <= B) l++;while(a[r+1].t <= R && r < D) r++;int id_l = B-l+1 , id_r = max( 0 , r - C + 1 );rep(j,0,b[i].c) ans[b[i].id] = max( ans[b[i].id] , dp[0][id_l][j] + dp[1][id_r][b[i].c - j] );}return;
}
void work() {int l,r,L,R,ll,rr,last_l,last_r;l=1;r=0;ll=1;rr=0;int T = 1-p;while(T <= b[q].t-p+1) {T += p;L = T-p+1; R = T+p-1; //????????? [T-p+1~T+p-1]while(a[l].t < L && l <= n) l++;while(a[r+1].t <= T && r < n) r++;  //????? [L,T]while( b[ll].t < L && ll <= q ) ll++;while( b[rr+1].t <= R && rr < q ) rr++; //host [L,R]int v_max=0;   rep(i,ll,rr) v_max = max(v_max,b[i].c);repp(i,r,l) {int id = r-i+1;repp(j,v_max,a[i].c) dp[0][id][j] = max( dp[0][id-1][j] , dp[0][id-1][j-a[i].c] + a[i].v );repp(j,a[i].c-1,0) dp[0][id][j] = dp[0][id-1][j];}//??dplast_l = l; last_r = r;while(a[l].t <= T && l <= n) l++;while(a[r+1].t <= R && r < n) r++; //????? (T,R]rep(i,l,r) {int id = i-l+1;repp(j,v_max,a[i].c)dp[1][id][j] = max( dp[1][id-1][j] , dp[1][id-1][j-a[i].c] + a[i].v );repp(j,a[i].c-1,0) dp[1][id][j] = dp[1][id-1][j];}//??dpmerge(last_l,last_r,l,r,ll,rr);rep(i,1,last_r-last_l+1) rep(j,0,v_max) dp[0][i][j] = 0;rep(i,1,r-l+1) rep(j,0,v_max) dp[1][i][j] = 0;l = last_r+1; r = last_r; ll = rr+1;}rep(i,1,q) printf("%d\n",ans[i]);
}
int main() {init();work();return 0; 
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！