ZOJ 1554 Folding

2760648 2008-02-25 15:11:56 Accepted 1554 C++ 00:00.56 980K C.D.=.=


做了两天的一道DP题。本来也是做不出的,幸好世界上有一种叫做大牛的恐怖生物。AndyZh和ZC果然强悍,在两年前就已经把这道题解决了。

贴个ZC的解题报告:

这题是一道最优化问题,此类问题一般使用搜索和动态规划,这题显然可以使用后者。
我们先来看看一个简单的例子: AAAAABBBBCCCCCDDDD,显然压缩后为
5
A4B5C4D)。

我们先不考虑这个串是如何压缩的,我们先考虑它是怎么组成的,显然它由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, 我们将它们折叠以后,可以得到: 3AAAABCBCBC), 但很明显 AAAABCBCBC还可以继续折叠,成为34A3BC))
 

所以在这里,我们处理Value [ I , j ]这个函数的时候,就要利用一下以前DP出的结果。
假如 S [ IJ ] 最多能够折叠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 ( intintint );    //预处理时检查能否折叠成K长度
int get ( intint );    //得到最小长度
void print ();    
void out ( intint );    //递归输出i开始j长度字符串
void sub ( intint );    //输出某一段

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] );
}


posted on 2008-02-25 15:21 杜仲当归 阅读(204) 评论(0)  编辑 收藏 引用 所属分类: 动态规划

只有注册用户登录后才能发表评论。

导航

<2008年2月>
272829303112
3456789
10111213141516
17181920212223
2425262728291
2345678

统计

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜