自动搬运

查看原文

来自洛谷，原作者为

	C1942huangjiaxu 我将终究顺流入大海

搬运于2025-08-24 22:56:44，当前版本为作者最后更新于2024-05-15 20:35:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑 $c_i=0$ 时怎么做。

那么相当于我们每次会根据 $x$ 的符号乘上一个数。

进行状压 DP，考虑需要记录哪些值。

对最终答案有负贡献时，我们希望 $|x|$ 尽量小，对最终答案有正贡献时，我们希望 $|x|$ 尽量大。

因此我们记录 $x\ge 0$ 的 $\max x,\min x$ 和 $x\le 0$ 的 $\max x,\min x$ 四个值就行了。

当 $c$ 不等 $0$ 时，除了上述的四个值，所有可能到达函数零点的值都要记录。

注意到函数零点的绝对值不超过 $c$，并且每次操作 $|x|$ 最多减少 $c$，因此我们只要额外记录 $|x|\le nc$ 的 $x$ 就可以了。

时间复杂度 $O(2^n n^2 c)$。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int V=225;
typedef __int128 LL;
int n,a[15],b[15],c[15],s;
bool f[1<<15][2*V+5];
LL f1[1<<15],f2[1<<15],f3[1<<15],f4[1<<15];
void write(LL x){
	if(x>=10)write(x/10);
	putchar('0'+x%10);
}
inline LL abs(LL x){
	return x<0?-x:x;
}
inline LL F(int i,LL x){
	return abs(x)*a[i]+x*b[i]+c[i];
}
inline void chg1(int S,LL v){
	f1[S]=max(f1[S],v);
}
inline void chg2(int S,LL v){
	if(v<0)return;
	if(!f2[S]||f2[S]>v)f2[S]=v;
}
inline void chg3(int S,LL v){
	f3[S]=min(f3[S],v);
}
inline void chg4(int S,LL v){
	if(v>0)return;
	if(!f4[S]||f4[S]<v)f4[S]=v;
}
inline void chg(int S,LL v){
	chg1(S,v),chg2(S,v),chg3(S,v),chg4(S,v);
	if(abs(v)<=V)f[S][v+V]=true;
}
int main(){
	scanf("%d%d",&n,&s);
	for(int i=0;i<n;++i)scanf("%d%d%d",&a[i],&b[i],&c[i]);
	if(s<0)f3[0]=f4[0]=s;
	if(s>0)f1[0]=f2[0]=s;
	f[0][s+V]=true;
	for(int S=0;S<(1<<n)-1;++S)
		for(int i=0;i<n;++i)if(!(S>>i&1)){
			int T=S|1<<i;
			if(f1[S]>0)chg(T,F(i,f1[S])),chg(T,F(i,f2[S]));
			if(f3[S]<0)chg(T,F(i,f3[S])),chg(T,F(i,f4[S]));
			for(int j=-V;j<=V;++j)if(f[S][j+V])chg(T,F(i,j));
		}
	if(f1[(1<<n)-1])write(f1[(1<<n)-1]);
	else putchar('-'),write(-f4[(1<<n)-1]);
	return 0;
}