题解：P10303 [THUWC 2020] 报告顺序

C1942huangjiaxu · 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;
}