BZOJ 1084 最大子矩阵

时间：2022-12-11 16:43:22

http://www.lydsy.com/JudgeOnline/problem.php?id=1084

思路:分m=1和m=2操作

 #include<algorithm>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<iostream>

 int f[][],F[][][];

 int sum[],sum1[],sum2[],n,m,K;

 int read(){

     int t=,f=;char ch=getchar();

     while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}

     while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}

     return t*f;

 }

 void sxpianfen1(){

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

      {int x=read();sum[i]=sum[i-]+x;}

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

      for (int k=;k<=K;k++){

       f[i][k]=f[i-][k];

       for (int j=;j<i;j++)

        f[i][k]=std::max(f[i][k],f[j][k-]+sum[i]-sum[j]);

     }

     printf("%d\n",f[n][K]);

 }

 void sxpianfen2(){

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

         int x=read(),y=read();

         sum1[i]=sum1[i-]+x;

         sum2[i]=sum2[i-]+y;

     }

     for (int k=;k<=K;k++)

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

       for (int j=;j<=n;j++){

          F[i][j][k]=std::max(F[i-][j][k],F[i][j-][k]);

          for (int l=;l<i;l++) F[i][j][k]=std::max(F[i][j][k],F[l][j][k-]+sum1[i]-sum1[l]);

          for (int l=;l<j;l++) F[i][j][k]=std::max(F[i][j][k],F[i][l][k-]+sum2[j]-sum2[l]);

          if (i==j)

          for (int l=;l<i;l++) F[i][j][k]=std::max(F[i][j][k],F[l][l][k-]+sum1[i]+sum2[j]-sum1[l]-sum2[l]);

       }

     printf("%d\n",F[n][n][K]);

 }

 int main(){

     n=read();m=read();K=read();

     if (m==){

         sxpianfen1();

     }else

         sxpianfen2();

 }

相关文章