学步园

传送门：【codeforces】477C Dreamoon and Strings

题目分析：

看起来像是一个贪心，但其实是DP。

因为每一次操作（删除0个，删除1个，删除2个...等）都是独立的。

现在，我们设母串长度为n，子串长度为m。

设dp[i][j]表示母串匹配到第i个字符可以得到j个不重复的子串时所需要删除的最少的字符。

假设我们现在遍历到第i个字符，且这个字符与子串第一个字符匹配，首先假设从这个位置开始还能得到一个子串，设该串的结尾位置为ii，那么得到这个子串的代价为ii - i + 1 - m。

此时转移方程便是：

i > 0：dp[ii][j] = min { dp[ii][j] , dp[i - 1][j - 1] + ii - i + 1 - m | 1 <= j <= n } ；

i = 0：dp[ii][j] = ii - i + 1 - m ；

（如果从第i个位置开始匹配不到子串，则上面的转移便不需要了。）

然后还有一次转移：

i > 0：dp[i][j] = min { dp[i][j] , dp[i - 1][j] | 0 <= j <= n } ；

（这个转移从头到尾一直需要，除了i = 0时。）

这样答案基本就出来了。

扫一遍dp[n - 1][i]，dp[n - 1][i]即删除dp[n - 1][i]个字符才能得到i个子串。

当达到最大以后，无用字符已经删除完毕，接下来再删除只能从子串中删除，易知每m个字符子串个数减一。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

typedef long long LL ;

#pragma comment(linker, "/STACK:1024000000")
#define rep( i , a , b ) for ( int i = a ; i <  b ; ++ i )
#define For( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define rev( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define travel( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next )
#define clr( a , x ) memset ( a , x , sizeof a )
#define CPY( a , x ) memcpy ( a , x , sizeof a )

const int MAXN = 2005 ;
const int INF = 0x3f3f3f3f ;

char s[MAXN] ;
char p[MAXN] ;
int dp[MAXN][MAXN] ;
int ans[MAXN] ;
int n , m ;

void solve () {
	n = strlen ( s ) ;
	m = strlen ( p ) ;
	clr ( dp , INF ) ;
	clr ( ans , 0 ) ;
	dp[0][0] = 0 ;
	int flag = 0 ;
	rep ( i , 0 , n ) {
		int ii = i , j = 0 ;
		if ( i ) For ( k , 0 , n ) dp[i][k] = min ( dp[i][k] , dp[i - 1][k] ) ;
		if ( !flag && s[ii] == p[j] ) {
			while ( ii < n && j < m ) {
				if ( s[ii] == p[j] ) ++ j ;
				++ ii ;
			}
			if ( j < m ) {
				flag = 1 ;
				continue ;
			}
			-- ii ;
			int tmp = ii - i + 1 - m ;
			//printf ( "%d %d %d\n" , ii , i , m ) ;
			if ( i ) {
				For ( k , 1 , n ) {
					dp[ii][k] = min ( dp[ii][k] , dp[i - 1][k - 1] + tmp ) ;
				}
			} else dp[ii][1] = tmp ;
		}
	}
	int max_match = 0 ;
	For ( i , 1 , n ) {
		if ( dp[n - 1][i] != INF ) {
			max_match = i ;
			ans[dp[n - 1][i]] = i ;
		} else break ;
	}
	max_match *= m ;
	int x = ans[0] ;
	For ( i , 0 , n ) {
		if ( n - i < max_match ) printf ( "%d" , ( n - i ) / m ) ;
		else printf ( "%d" , x = max ( ans[i] , x ) ) ;
		if ( i < n ) printf ( " " ) ;
		else printf ( "\n" ) ;
	}
}

int main () {
	while ( ~scanf ( "%s%s" , s , p ) ) solve () ;
	return 0 ;
}