Warning: session_start(): open(/tmp/sess_eaa898124ecad33b0b8c678f7b40b2be, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/8/8fe637ac40e9dfa91f93fbcd08d065e4.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 牛客练习赛77 ======
[[https://ac.nowcoder.com/acm/contest/11169|比赛链接]]
===== E-小G的数学难题 =====
==== 题意 ====
给定长度为 $n$ 的序列 $A,B,C$ 以及 $p$。
其中 $A=\sum_{i=1}^n a_ix_i,B=\sum_{i=1}^n b_ix_i,C=\sum_{i=1}^n c_ix_i,x_i=0/1$。
问满足 $A\le p,B\ge p$ 时 $C$ 的最小值。
==== 题解 ====
设 $\text{dp}(i,p)$ 表示满足 $\sum_{j=1}^n a_jx_j\le p,\sum_{j=1}^n b_jx_j\ge p$ 时 $\sum_{j=1}^n c_jx_j$ 的最小值。
于是有状态转移方程
$$
\text{dp}(i,p)\gets\min(\text{dp}(i-1,p),\min(\text{dp}(i-1,p-b_i\sim p-a_i))+c_i)
$$
单调队列维护即可，时间复杂度 $O(np)$。
const int MAXN=1e3+5,MAXP=1e4+5,Inf=2e9+5;
int a[MAXN],b[MAXN],c[MAXN],dp[2][MAXP],que[MAXP];
int main()
{
int T=read_int();
while(T--){
int n=read_int(),p=read_int();
_for(i,0,n)a[i]=read_int();
_for(i,0,n)b[i]=read_int();
_for(i,0,n)c[i]=read_int();
int pos=0;
_rep(i,0,p)dp[pos][i]=Inf;
dp[pos][0]=0;
_for(i,0,n){
pos=!pos;
int head=0,tail=-1;
_rep(j,0,p){
dp[pos][j]=dp[!pos][j];
while(head<=tail&&que[head]=0){
while(head<=tail&&dp[!pos][que[tail]]>=dp[!pos][j-a[i]])tail--;
que[++tail]=j-a[i];
}
if(head<=tail)
dp[pos][j]=min(dp[pos][j],dp[!pos][que[head]]+c[i]);
}
}
if(dp[pos][p]==Inf)
puts("IMPOSSIBLE!!!");
else
enter(dp[pos][p]);
}
return 0;
}