题目
点这里看题目。
分析
首先可以考虑一个比较粗糙的大 DP ：
(f(i,j))：前(i)行，刷(j)次，最多能刷的正确格子数。
转移是一个背包：
[f(i,j)=max_{1le kle m}{f(i-1,j-k)+con(i,k)}
]
其中(con(i,k))表示第(i)行刷(k)次最多能刷的正确格子数。
我们发现，由于(con)是按行独立的，因此对于每行我们可以再做一次 DP 处理出(con)。
对于第(i)行，我们有如下的 DP ：
(g(j,k))：前(j)个格子刷(k)次最多能刷的正确格子数。
设(mx(j,k))为第(i)行刷一次区间([j,k])最多能刷的正确格子数，也就是区间内数量最多的颜色的数量。
转移显然：
[g(j,k)=max_{0le l< j}{g(l,k-1)+mx(l+1,j)}
]
内层 DP 一次(O(m^3))，做(n)次就是(O(nm^3))；外层 DP (O(nmT))。总时间(O(nm^3+nmT))。
代码
#include <cstdio>
const int INF = 0x3f3f3f3f;
const int MAXN = 55, MAXM = 55, MAXT = 2505;
template<typename _T>
void read( _T &x )
{
x = 0;char s = getchar();int f = 1;
while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
if( 9 < x ){ write( x / 10 ); }
putchar( x % 10 + '0' );
}
template<typename _T>
_T MAX( const _T a, const _T b )
{
return a > b ? a : b;
}
int g[MAXM][MAXM], f[MAXT];
int col[MAXN][MAXM];
int N, M, T;
int main()
{
read( N ), read( M ), read( T );
for( int i = 1 ; i <= N ; i ++ )
for( int j = 1 ; j <= M ; j ++ )
scanf( "%1d", &col[i][j] );
for( int i = 1 ; i <= T ; i ++ ) f[i] = -INF;
for( int i = 1 ; i <= M ; i ++ ) g[0][i] = -INF;
for( int i = 1 ; i <= N ; i ++ )
{
for( int j = 1 ; j <= M ; j ++ )
for( int k = 1 ; k <= j ; k ++ )
{
g[j][k] = -INF; int cnt[2] = {};
for( int l = j - 1 ; ~ l ; l -- )
cnt[col[i][l + 1]] ++, g[j][k] = MAX( g[j][k], g[l][k - 1] + MAX( cnt[0], cnt[1] ) );
}
for( int j = T ; j ; j -- )
for( int k = 1 ; k <= M && k <= j ; k ++ )
f[j] = MAX( f[j], f[j - k] + g[M][k] );
}
write( f[T] ), putchar( '
' );
return 0;
}