BZOJ1296(SCOI 2009)[브러시 장인] - 가방+DP

bzoj1296
[문제풀이 보고]
가방의 정의 g[i][j]는 현재 i행을 밀어서 모두 j회 갱신했다는 것을 쉽게 생각할 수 있다.
그리고 우리는 다시 한 줄 한 줄을 고려한다.
정의 f[i][j]는 현재 i개로 미루고 j차의 최우선을 나타냈다.
그래서 DP 두 개가 해결됐어요.

#include
#include
using namespace std;
const int maxn=55,maxm=2505;
int n,m,T,ans,sum[maxn],g[maxn][maxm],f[maxn][maxn];
bool a[maxn][maxn];
int main()
{
    freopen("1296.in","r",stdin);
    freopen("1296.out","w",stdout);
    scanf("%d%d%d",&n,&m,&T);
    for (int i=1; i<=n; i++)
     for (int j=1; j<=m; j++)
      {
        char ch=getchar();
        while (ch!='1'&&ch!='0') ch=getchar();
        a[i][j]=ch-48;
      }
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=m; j++) sum[j]=sum[j-1]+a[i][j];
        for (int j=1; j<=m; j++)
         for (int s=1; s<=m; s++)
          {
            f[s][j]=0;
            for (int t=0,num; t
             num=sum[s]-sum[t],f[s][j]=max(f[s][j],f[t][j-1]+max(num,s-t-num));
          }
        for (int j=1; j<=T; j++)
         for (int k=0,gl=min(j,m); k<=gl; k++)
          g[i][j]=max(g[i][j],g[i-1][j-k]+f[m][k]);
    }
    ans=0; for (int i=1; i<=T; i++) ans=max(ans,g[n][i]);
    printf("%d",ans);
    return 0;
}