正题

题目链接:https://ac.nowcoder.com/acm/contest/11169/E

题目大意

给出\(n\)个三元组\((a_i,b_i,c_i)\)。

要求选出一个集合\(S\)，要求

\[\left(\sum_{i\in S}a_i\right)\leq P,\left(\sum_{i\in S}b_i\right)\geq P
\]

且最小化\(\sum_{i\in S}c_i\)

\(1\leq T\leq 5,1\leq n\leq 1000,1\leq P\leq 10000,1\leq a_i\leq b_i\leq 2\times 10^6,1\leq c_i\leq 2\times 10^6\)

解题思路

暴力的思路是设\(f_{i,l,r}\)表示到第\(i\)个，\(a_i\)的和为\(l\)，\(b_i\)的和为\(r\)时的最小值。

但是这个\(O(nP^2)\)的显然不行，发现有一个\(a_i\leq b_i\)的性质考虑怎么使用。

其实还要一个相关的性质就是两个的限制的\(P\)是相等的，虽然看起来比较废话但确实是有用的。

一个十分巧妙的\(dp\)是设\(f_{i,j}\)表示\(a_i\)的和\(\leq j\)且\(b_i\)的和\(\geq j\)。虽然这样的限制不完全，但是这样确实可以统计到最小答案且不会统计到更小答案。

转移就是

\[f_{i,j}=min\{f_{i-1,j},f_{i-1,p}+c_i\}(p\in[j-b_i,j-a_i])
\]

这样每一层用单调队列维护就可以了

时间复杂度\(O(TnP)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const ll N=1100;

ll T,n,P,a[N],b[N],c[N],f[N][N*10],q[N*10];

signed main()

{

	scanf("%lld",&T);

	while(T--){

		scanf("%lld%lld",&n,&P);

		for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);

		for(ll i=1;i<=n;i++)scanf("%lld",&b[i]);

		for(ll i=1;i<=n;i++)scanf("%lld",&c[i]);

		memset(f,0x3f,sizeof(f));f[0][0]=0;

		for(ll i=1;i<=n;i++){

			ll tail=0,head=1,z=-1;

			for(ll j=0;j<=P;j++){

				f[i][j]=f[i-1][j];

				ll l=j-b[i],r=j-a[i];

				while(z<r){

					z++;

					if(f[i-1][z]>=1e18)continue;

					while(head<=tail&&f[i-1][q[tail]]>f[i-1][z])tail--;

					q[++tail]=z;

				}

				while(head<=tail&&q[head]<l)head++;

				if(head<=tail)f[i][j]=min(f[i][j],f[i-1][q[head]]+c[i]);

			}

		}

		if(f[n][P]>=1e18)printf("IMPOSSIBLE!!!\n");

		else printf("%lld\n",f[n][P]);

	}

	return 0;

}

巴特西

牛客练习赛79E-小G的数学难题【dp,单调队列】

正题

题目大意

解题思路

code

最新文章

热门文章