小G的数学难题

小G在APIO2021中遇到了一个数学难题，可是经过小G漫⻓的思索，发现还是始终不能窥见真谛。

具体描述下这个问题是这样的：有三个长度为 $n$ 的数列 $\left\{ a_{1}, a_{2}, . . . , a_{n} \right\}$ , $\left\{ b_{1}, b_{2}, . . . , b_{n} \right\}$ , $\left\{ c_{1}, c_{2}, . . . , c_{n} \right\}$ ，

需要满足约束：

1. $a_{1} \times x_{1}+a_{2} \times x_{2}+...+a_{n} \times x_{n} \leq P$

2. $b_{1} \times x_{1}+b_{2} \times x_{2}+...+b_{n} \times x_{n} \geq P$

3. $∀i, x_{i}∈\left\{ 0,1 \right\}$

然后题目要求小G最小化 $w=c_{1} \times x_{1}+c_{2} \times x_{2}+...+c_{n} \times x_{n}$ 。

可是距离比赛结束只剩下半个小时了，小G现在非常着急，能否A掉这题并取得AK的好成绩拿到AU，就靠你了，加油！

第一行一个正整数 $T$ 表示数据组数， $T\leq5$ 。

对于每组测试数据：

第一行两个正整数 $n$ , $P$ ，其中 $n\leq1000$ , $P\leq10000$ 。

第二行 $n$ 个非负整数，第 $i$ 个数为 $a_{i}$ 。

第三行 $n$ 个非负整数，第 $i$ 个数为 $b_{i}$ 。

第四行 $n$ 个非负整数，第 $i$ 个数为 $c_{i}$ 。

其中 $a_{i}$ , $b_{i}$ , $c_{i}$ 满足 $a_{i} \leq b_{i} \leq 2\times10^{6}$ , $c_{i}\leq 2\times10^{6}$ 。

5 5 26 3 3 2 10 1 7 10 13 16 3 5 10 4 6 2 5 25 1 3 6 10 13 13 7 8 15 16 2 3 10 2 7 5 1 2 9 7 2 4 4 10 7 6 7 0 0 0 0 0 5 7 2 6 1 9 11 7 11 12 16 16 1 7 8 4 5 5 24 9 1 13 7 4 13 14 14 13 6 7 6 5 8 2

#include <iostream> using namespace std; const int inf=2e9+1e5; int dp[1005][10005],a[1005],b[1005],c[1005],q[10005],head,tail; int main(int argc, char** argv) { int T; cin >> T; while(T--) { int n,p; cin >> n >> p; for(int i=1;i<=n;i++) cin >> a[i]; for(int i=1;i<=n;i++) cin >> b[i]; for(int i=1;i<=n;i++) cin >> c[i]; for(int i=1;i<=p;i++) dp[0][i]=inf; for(int i=1;i<=n;i++) { for(int j=0;j<=p;j++) dp[i][j]=dp[i-1][j]; head=1,tail=0; for(int j=a[i];j<=p;j++) { if(head<=tail&&q[head]<j-b[i]) ++head; while(head<=tail&&dp[i-1][q[tail]]>dp[i-1][j-a[i]]) --tail; q[++tail]=j-a[i]; dp[i][j]=min(dp[i][j],dp[i-1][q[head]]+c[i]); } } if(dp[n][p]>2e9) puts("IMPOSSIBLE!!!"); else cout << dp[n][p] << "\n"; } return 0; }

详情