bzoj 1084: [SCOI2005]最大子矩陣 題解

【原題】

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

Sample Output

【分析】照理來說是一個很簡單的DP。因為M<=2，所以明擺著分情況做。但是我開始寫的DP一直萎，不知道為什麼。後來去網上開了題解，發現我的想法和意義都是對的，但是轉移的時候我少了一維（詳見代碼）只能說呵呵了。雖然我和標解看上去都對，但是我還是想不通為什麼我的不可以。

【自己的想法】

#include
#include
#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;
}

#include
#include
#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