| 2760648 |
2008-02-25 15:11:56 |
Accepted
|
1554
|
C++ |
00:00.56 |
980K |
C.D.=.=
|
做了两天的一道DP题。本来也是做不出的，幸好世界上有一种叫做大牛的恐怖生物。AndyZh和ZC果然强悍，在两年前就已经把这道题解决了。
贴个ZC的解题报告：
这题是一道最优化问题，此类问题一般使用搜索和动态规划，这题显然可以使用后者。
我们先来看看一个简单的例子： AAAAABBBBCCCCCDDDD，显然压缩后为
5（A）4（B）5（C）4（D）。
我们先不考虑这个串是如何压缩的，我们先考虑它是怎么组成的，显然它由4个部分组成，它们分别为“AAAAA”、“BBBB”、“CCCCC”、“DDDD”，然后再将这四个部分分解得到。
则我们可以这样来动态规划： 我们先考虑将这个字符串分解，然后逐步将各个部分压缩后再组合得到最终的压缩串。 这个题目可以用经典的邮局问题的模型来解决：
Opt [ I , j ] = min ( Opt [ I , k ] + Value [ I + k , j - k ] ) , Opt [ I , j ] 表示从第I个字符开始取J个字符，分解成所得到的最小长度。
Value [ I+k , j-k ]表示S[i+k..i+j]折叠后的最小长度。
可是有这样一类串： AAAABCBCBCAAAABCBCBCAAAABCBCBC， 我们将它们折叠以后，可以得到： 3（AAAABCBCBC）， 但很明显 AAAABCBCBC还可以继续折叠，成为3（4（A）3（BC））
所以在这里，我们处理Value [ I , j ]这个函数的时候，就要利用一下以前DP出的结果。
假如 S [ I，J ] 最多能够折叠P次，则
Value [ I , j ] = Opt [ I , J Div P ] + Trunc ( Ln(P) / Ln(10) ) + 2 ( Trunc ( Ln(P) / Ln(10) ) + 2表示括号和P这些字符的长度)
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
int opt[100][100], fold[100][100], ch[100][100], L;
//对于i开始j长度字符串，分别保存dp值（最小长度）、字符串能折叠成的最小长度（K长度折叠）、
//和在哪里折叠
string str;
void dp ();
void init ();
int check ( int, int, int ); //预处理时检查能否折叠成K长度
int get ( int, int ); //得到最小长度
void print ();
void out ( int, int ); //递归输出i开始j长度字符串
void sub ( int, int ); //输出某一段
int main ()
{
//freopen ( "in.txt", "r", stdin );
while ( cin >> str )
{
init ();
dp ();
print ();
}
return 0;
}
void init ()
{
memset ( fold, 0, sizeof ( fold ) );
memset ( opt, 0, sizeof ( opt ) );
memset ( ch, 0, sizeof ( ch ) );
int i, j, k;
L = str.size ();
for ( i = 0; i < L; i ++ )
{
for ( j = 1; j + i <= L; j ++ )
{
fold[i][j] = j;
if ( j > 4 )
{
for ( k = 1; k <= j / 2; k ++ )
{
if ( j % k )
continue;
if ( check ( i, j, k ) )
{
fold[i][j] = k;
break;
}
}
}
}
}
}
int check ( int st, int len, int k )
{
int i;
string def = str.substr ( st, k );
for ( i = st + k; i < st + len; i += k )
{
if ( def != str.substr ( i, k ) )
return 0;
}
return 1;
}
void dp ()
{
int i, j, k, t;
for ( i = 0; i < L; i ++ )
{
for ( j = 1; j <= 4; j ++ )
{
opt[i][j] = j;
}
}
for ( j = 5; j <= L; j ++ )
{
for ( i = 0; i + j <= L; i ++ )
{
opt[i][j] = get ( i, j );
if ( opt[i][j] < j )
ch[i][j] = j;
for ( k = 1; k < j; k ++ )
{
t = opt[i][k] + get ( i + k, j - k );
if ( opt[i][j] > t )
{
ch[i][j] = k;
opt[i][j] = t;
}
}
}
}
}
int get ( int i, int j )
{
int x = fold[i][j];
if ( x < j )
return opt[i][x] + 3 + int ( log ( double ( j ) / double ( x ) ) / log ( 10.0 ) );
else if ( opt[i][j] )
return opt[i][j];
else
return j;
}
void print ()
{
//printf ( "%d\n", ch[0][10] );
out ( 0, L );
printf ( "\n" );
}
void out ( int i, int j )
{
if ( ch[i][j] == j )
{
int x = j / fold[i][j];
printf ( "%d", x );
printf ( "(" );
out ( i, fold[i][j] );
printf ( ")" );
}
else if ( ch[i][j] == 0 )
{
sub ( i, j );
}
else
{
int k = ch[i][j];
out ( i, k );
out ( i + k, j - k );
}
}
void sub ( int st, int l )
{
int i;
for ( i = 0; i < l; i ++ )
printf ( "%c", str[st + i] );
}