CF1209题解

E

对每列的元素计算最大值，降序排，显然取前\(min(n,m)\)个列处理即可

比较巧妙的动规，设\(f(i,S)\)为前\(i\)列，已经确定最大值集合为\(S\)的其集合的最大值\((\)通俗讲，对于每列，二进制枚举该列设定为最大值的行位置，该行其他值便不需要管了\()\)

考虑类似于背包的转换，对于每个\(S\)，填表法去填一个空位置，\(S\)从小到大枚举，即可

细节：滚动数组处理

#include<bits/stdc++.h>
typedef int LL;
const LL maxn=13,maxm=2e3+9;
inline LL Read(){
    LL x(0),f(1); char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1; c=getchar();
    }
    while(c>='0' && c<='9'){
        x=(x<<3)+(x<<1)+c-'0'; c=getchar();
    }return x*f;
}
struct node{
    LL x,id;
}M[maxm];
LL T;
LL a[maxn][maxm],f[1<<maxn],g[1<<maxn],tmp[1<<maxn],fg[maxm],pos[1<<maxn];
inline bool cmp(node xx,node yy){
    return xx.x>yy.x;
}
inline LL Lowbit(LL x){
    return x&(-x);
}
inline void Solve(LL n,LL m){
    for(LL i=1;i<=m;++i) M[i]=(node){0,i},fg[i]=0;
    for(LL i=1;i<=n;++i){
        for(LL j=1;j<=m;++j){
            a[i][j]=Read();
            M[j].x=std::max(M[j].x,a[i][j]);
        }
    }
    for(LL i=0;i<n;++i) pos[1<<i]=i+1;
    std::sort(M+1,M+1+m,cmp);
    for(LL i=1;i<=n && i<=m;++i)
        fg[M[i].id]=1;//,printf("%d ",M[i].id); puts("");
    LL Len(1<<n);
    for(LL i=0;i<Len;++i) f[i]=0;
    for(LL i=1;i<=m;++i){
        if(!fg[i]) continue;
        for(LL bit=0;bit<Len;++bit) tmp[bit]=0;

        for(LL j=1;j<=n;++j){
            for(LL bit=0;bit<Len;++bit) g[bit]=f[bit];
            for(LL bit=0;bit<Len;++bit){
                LL p(Len-1^bit);
                while(p){
                    LL x(Lowbit(p)); LL nw(pos[x]);
                    g[bit|x]=std::max(g[bit|x],g[bit]+a[nw][i]);
                    p-=x;
                }
            }
            LL tp(a[1][i]); for(LL k=1;k<n;++k) a[k][i]=a[k+1][i]; a[n][i]=tp;
            for(LL bit=0;bit<Len;++bit) tmp[bit]=std::max(tmp[bit],g[bit]);
        }
        for(LL bit=0;bit<Len;++bit) f[bit]=tmp[bit];
    }
    printf("%d\n",f[Len-1]);
}
int main(){
    T=Read();
    while(T--){
        LL n(Read()),m(Read());
        Solve(n,m);
    }
    return 0;
}/*

3
2 3
2 5 7
4 2 4
3 6
4 1 5 2 10 4
8 6 6 4 9 10
5 4 9 5 8 7
3 3
9 9 9
1 1 1
1 1 1
*/