====== 牛客练习赛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)$。

<hidden 查看代码>
<code cpp>
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]<j-b[i])head++;
				if(j-a[i]>=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;
}
</code>
</hidden>