luogu P5322 [BJOI2019]排兵布阵

时间：2023-03-09 07:14:43
luogu P5322 [BJOI2019]排兵布阵

传送门

普及dp

设\(f_{i,j}\)表示前\(i\)个城堡,用\(j\)人的最大价值,转移枚举一个对手,如果这个对手在\(i\)这个城堡人数是第\(k\)小的,那么用\(2a_i+1\)人可以得到\(ik\)的价值

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<vector>

#include<cmath>

#include<ctime>

#include<queue>

#include<map>

#include<set>

#define LL long long

#define db double

using namespace std;

const int N=20000+10,M=100+10,inf=1<<29;

int rd()

{

    int x=0,w=1;char ch=0;

    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

int kk,n,m,f[2][N],a[M][M];

int main()

{

    kk=rd(),n=rd(),m=rd();

    for(int j=1;j<=kk;++j)

        for(int i=1;i<=n;++i)

            a[i][j]=rd();

    memset(f,-0x3f3f3f,sizeof(f));

    int nw=1,la=0;

    f[la][0]=0;

    for(int i=1;i<=n;++i)

    {

        sort(a[i]+1,a[i]+kk+1);

        for(int j=0;j<=m;++j)

        {

            if(f[la][j]<=-inf) continue;

            f[nw][j]=max(f[nw][j],f[la][j]);

            for(int k=1;k<=kk&&j+a[i][k]*2+1<=m;++k)

                f[nw][j+a[i][k]*2+1]=max(f[nw][j+a[i][k]*2+1],f[la][j]+i*k);

            f[la][j]=-inf;

        }

        nw^=1,la^=1;

    }

    int ans=-inf;

    for(int j=0;j<=m;++j) ans=max(ans,f[la][j]);

    printf("%d\n",ans);

    return 0;

}

相关文章