大意

有 $n$ 个物品，每个物品有三个权值 $a_i$，$b_i$，$c_i$。

要从这选出 $m$ 个物品，将它们这三个权值分别求和记为 $A$，$B$，$C$。

求最大的 $|A| + |B| + |C|$。

思路

考虑如何去掉绝对值：我们枚举三个绝对值里分别是正数还是负数，直接去掉绝对值。

一共有 $8$ 种情况，一一动态规划求解即可。

即使枚举时可能无法使最后结果是非负数，但由于这样不优，不影响计算。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,s,l;
#define f(i,j,k) for(register int i=j;i<=k;++i)
#define g(i,j,k) for(register int i=j;i>=k;--i)
#define pos(i,j) (((i>>(j-1)&1ll)==1?1ll:-1ll))
void Max(long long& x,long long y){if(x<y)x=y;}
long long a[1010],b[1010],c[1010];
long long dp[1010][1010][8],ans;
int main(){
    cin>>n>>m;
    f(i,1,n)scanf("%lld %lld %lld",&a[i],&b[i],&c[i]);
    f(j,1,m)f(k,0,7)dp[0][j][k]=-101010101010101010;
    f(i,1,n)f(j,1,m)f(k,0,7){
        dp[i][j][k]=-101010101010101010;
        Max(dp[i][j][k],dp[i-1][j][k]);
        Max(dp[i][j][k],dp[i-1][j-1][k]+pos(k,1)*a[i]+pos(k,2)*b[i]+pos(k,3)*c[i]);
    }
    f(k,0,7)Max(ans,dp[n][m][k]);
    printf("%lld\n",ans);
    return 0;
}