bzoj 1084: [SCOI2005]最大子矩阵例题

bzoj 1084: [SCOI2005]最大子矩阵题解

【原题】

1084: [SCOI2005]最大子矩阵

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1016 Solved: 518
[Submit][Status]

Description

这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠。

Input

第一行为n,m,k（1≤n≤100,1≤m≤2,1≤k≤10），接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。

Output

只有一行为k个子矩阵分值之和最大为多少。

Sample Input

3 2 2
1 -3
2 3
-2 3

Sample Output

【分析】照理来说是一个很简单的DP。因为M<=2，所以明摆着分情况做。但是我开始写的DP一直萎，不知道为什么。后来去网上开了题解，发现我的想法和意义都是对的，但是转移的时候我少了一维（详见代码）只能说呵呵了。虽然我和标解看上去都对，但是我还是想不通为什么我的不可以。

【自己的想法】

#include<cstdio>
#include<algorithm>
#define N 105
#define K 15
using namespace std;
int s[N],sum1[N],sum2[N],g[N][K],f[N][N][K];
int n,m,ans,L;
inline int max3(int x,int y,int z){return max(max(x,y),z);}
inline int max4(int x,int y,int p,int q){return max(max(x,y),max(p,q));}
void solve_1()
{
  for (int i=1;i<=n;i++) scanf("%d",&s[i]);
  for (int i=1;i<=n;i++)
  {
    g[i][1]=g[i-1][1]+s[i];
    for (int j=2;j<=L;j++)
      g[i][j]=max3(g[i-1][j],g[i-1][j]+s[i],g[i-1][j-1]+s[i]);
  }
  ans=g[n][L];
}
void solve_2()
{
  for (int i=1;i<=n;i++) scanf("%d%d",&sum1[i],&sum2[i]);
  for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++)
    {
      f[i][j][1]=f[i-1][j-1][1]+sum1[i]+sum2[j];
      for (int k=2;k<=L;k++)  
      {
        f[i][j][k]=max3(f[i-1][j][k],f[i-1][j][k]+sum1[i],f[i-1][j][k-1]+sum1[i]);
        f[i][j][k]=max4(f[i][j][k],f[i][j-1][k],f[i][j-1][k]+sum2[j],f[i][j-1][k-1]+sum2[j]);
        if (i==j) 
        f[i][j][k]=max4(f[i][j][k],f[i-1][j-1][k],f[i-1][j-1][k]+sum1[i]+sum2[j],f[i-1][j-1][k-1]+sum1[i]+sum2[j]);
      }
    }
  ans=f[n][n][L];
}
int main()
{
  scanf("%d%d%d",&n,&m,&L);
  if (m==1) solve_1();
  if (m==2) solve_2();
  printf("%d",ans);
  return 0;
}

【AC代码】

#include<cstdio>
#include<algorithm>
#define N 105
#define K 15
using namespace std;
int s[N],sum1[N],sum2[N],g[N][K],f[N][N][K];
int n,m,ans,L;
void solve_1()
{
  for (int i=1;i<=n;i++) scanf("%d",&s[i]),s[i]+=s[i-1];
  for (int i=1;i<=n;i++)
    for (int k=1;k<=L;k++)
    {
      g[i][k]=g[i-1][k];
      for (int j=0;j<i;j++)
        g[i][k]=max(g[i][k],g[j][k-1]+s[i]-s[j]);
    }   
  ans=g[n][L];
}
void solve_2()
{
  for (int i=1;i<=n;i++) 
    scanf("%d%d",&sum1[i],&sum2[i]),sum1[i]+=sum1[i-1],sum2[i]+=sum2[i-1];
  for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++)
      for (int k=1;k<=L;k++)
      {
        f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k]);
        for (int p=0;p<i;p++)
          f[i][j][k]=max(f[i][j][k],f[p][j][k-1]+sum1[i]-sum1[p]);
        for (int p=0;p<i;p++)
          f[i][j][k]=max(f[i][j][k],f[i][p][k-1]+sum2[j]-sum2[p]);
        if (i==j) for (int p=0;p<i;p++)
          f[i][j][k]=max(f[i][j][k],f[p][p][k-1]+sum1[i]+sum2[j]-sum1[p]-sum2[p]);
      }
  ans=f[n][n][L];
}
int main()
{
  scanf("%d%d%d",&n,&m,&L);
  if (m==1) solve_1();
  if (m==2) solve_2();
  printf("%d",ans);
  return 0;
}

bzoj 1084: [SCOI2005]最大子矩阵 例题