Codeforces Gym 100002 Problem F "Folding" 区间DP

时间:2021-10-27 06:49:04

Problem F "Folding"

Time Limit: 1 Sec

Memory Limit: 256 MB

题目连接

http://codeforces.com/gym/100002

Description

Bill is trying to compactly represent sequences of capital alphabetic characters from 'A' to 'Z' by folding repeating subsequences inside them. For example, one way to represent a sequence AAAAAAAAAABABABCCD is 10(A)2(BA)B2(C)D. He formally defines folded sequences of characters along with the unfolding transformation for them in the following way:

  • A sequence that contains a single character from 'A' to 'Z' is considered to be a folded sequence. Unfolding of this sequence produces the same sequence of a single character itself.
  • If S and Q are folded sequences, then SQ is also a folded sequence. If S unfolds to S' and Q unfolds to Q', then SQ unfolds to S'Q'.
  • If S is a folded sequence, then X(S) is also a folded sequence, where X is a decimal representation of an integer number greater than 1. If S unfolds to S', then X(S) unfolds to S' repeated X times.

According to this definition it is easy to unfold any given folded sequence. However, Bill is much more interested in the reverse transformation. He wants to fold the given sequence in such a way that the resulting folded sequence contains the least possible number of characters.

Input

The input file contains a single line of characters from 'A' to 'Z' with at least 1 and at most 100 characters.

Output

Write to the output file a single line that contains the shortest possible folded sequence that unfolds to the sequence that is given in the input file. If there are many such sequences then write any one of them.

Sample Input

AAAAAAAAAABABABCCD

Sample Output

9(A)3(AB)CCD

HINT

 

题意

就是相同的可以被压缩,问你最少压缩成什么样子(注意,括号和数字也算长度

题解:

区间DP,维护区间DP的时候,同时维护一下这个区间的字符串是什么样子的就好了

代码:

//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <bitset>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 110000
#define mod 10007
#define eps 1e-9
#define pi 3.1415926
int Num;
//const int inf=0x7fffffff; //§ß§é§à§é¨f§³
const ll Inf=0x3f3f3f3f3f3f3f3fll;
inline ll read()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
//************************************************************************************** string s[][];
int n;
int dp[][];
int vis[][];
char S[];
int FF(int x)
{
int add=;
while(x)
{
add++;
x/=;
}
return add;
}
string F(int x)
{
string ss;
while(x)
{
ss+=(char)(x%+'');
x/=;
}
reverse(ss.begin(),ss.end());
return ss;
}
int solve(int l,int r)
{
if(vis[l][r])return dp[l][r];
vis[l][r]=;
for(int i=l;i<r;i++)
{
if(dp[l][r]>solve(l,i)+solve(i+,r))
{
dp[l][r]=dp[l][i]+dp[i+][r];
s[l][r]=s[l][i]+s[i+][r];
}
}
for(int i=;i<r-l+;i++)
{
if((r-l+)%(i)!=)
continue;
int add = ;
for(int k=;;k++)
{
if((k+)*i>r-l+)
break;
for(int j=;j<i;j++)
{
if(S[l+k*i+j]!=S[l+j])
break;
if(j==i-)
add+=;
}
} if(add==(r-l+)/i)
{
int point=solve(l,l+i-)++FF(add);
if(dp[l][r]>point)
{
dp[l][r]=point;
s[l][r]="";
s[l][r]+=F(add)+'(';
s[l][r]+=s[l][()*i-+l];
s[l][r]+=')';
}
}
}
return dp[l][r];
}
int main()
{
freopen("folding.in","r",stdin);
freopen("folding.out","w",stdout);
scanf("%s",S+);
n = strlen(S+);
for(int i=;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
dp[i][j]=j-i+;
for(int k=;k<j-i+;k++)
{
s[i][j]+=S[i+k];
}
}
}
solve(,n);
cout<<s[][n]<<endl;
return ;
}

Codeforces Gym 100002 Problem F "Folding" 区间DP的更多相关文章

  1. Codeforces Gym 100286F Problem F&period; Fibonacci System 数位DP

    Problem F. Fibonacci SystemTime Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://acm.hust.edu.cn/vjudg ...

  2. Codeforces Gym 100500F Problem F&period; Door Lock 二分

    Problem F. Door LockTime Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://codeforces.com/gym/100500/at ...

  3. Educational Codeforces Round 61 F 思维 &plus; 区间dp

    https://codeforces.com/contest/1132/problem/F 思维 + 区间dp 题意 给一个长度为n的字符串(<=500),每次选择消去字符,连续相同的字符可以同 ...

  4. Codeforces Gym 100002 D&quot&semi;Decoding Task&quot&semi; 数学

    Problem D"Decoding Task" Time Limit: 1 Sec Memory Limit: 256 MB 题目连接 http://codeforces.com ...

  5. Codeforces Gym 100002 B Bricks 枚举角度

    Problem B Bricks" Time Limit: 1 Sec Memory Limit: 256 MB 题目连接 http://codeforces.com/gym/100002 ...

  6. Codeforces Gym 100002 E &quot&semi;Evacuation Plan&quot&semi; 费用流

    "Evacuation Plan" Time Limit: 1 Sec Memory Limit: 256 MB 题目连接 http://codeforces.com/gym/10 ...

  7. Codeforces Gym 100002 C &quot&semi;Cricket Field&quot&semi; 暴力

    "Cricket Field" Time Limit: 1 Sec Memory Limit: 256 MB 题目连接 http://codeforces.com/gym/1000 ...

  8. Codeforces 758D Ability To Convert(区间DP)

    题目链接:http://codeforces.com/problemset/problem/758/D 题意:一个n进制下的数k,其中k不会用字母,如果有A就用10代替了.求k这个数对应的,在10进制 ...

  9. UVA1630 Folding 区间DP

    Folding Description   Bill is trying to compactly represent sequences of capital alphabetic characte ...

随机推荐

  1. 锋利的jQuery书中推荐的几款插件

    1.jQuery表单验证插件——Validation 2.jQuery表单插件——Form 3.模态窗口插件——SimpleModal 4.管理Cookie的插件——Cookie 5.jQuery U ...

  2. iftop命令命令详解

    iftop命令命令详解 作者:尹正杰 版权声明:原创作品,谢绝转载!否则将追究法律责任. 在Linux命令中有很多内置命令,和外置命令,但是内部命令的功能毕竟是有限的,比如ifconfig,它就不能看 ...

  3. 常用vim设置

    set tabstop=4set shiftwidth=4set expandtabset hlsearchset cindent set autoindent set tabstop=4是设TAB宽 ...

  4. Android Activity使用拾遗

    一.onWindowFocusChanged 有时我们需要测量一个Activity多长时间才能显示出来,那么在代码中打点计时的时机选在哪儿呢?在onCreate和onResume执行完成后,Activ ...

  5. maven下载jta失败,自己本地安装jta库

    mvn install:install-file -Dfile=./jta-1_0_1B-classes.zip -DgroupId=javax.transaction -DartifactId=jt ...

  6. 模型驱动 ModelDriven

    ModelDriven:模型驱动,对所有action的模型对象进行批处理. 我们在开发中, 在action中一般是用实体对象,然后给实体对象get,set方法. RegAction{ User use ...

  7. SQLServer Merger Using语法使用和注意点

    SQL多表关联数据更新,如果数据量比较少的情况下,用Update也是可以的:脚本如下: UPDATE NA_AgentGrpOrder SET AttrServSIItem=b.AttrValue F ...

  8. 360大牛:全面解读PHP面试

    让大家了解基本面试流程和面试的核心要求以及意义是什么并理解PHP面试考点主要以基础为核心,说明PHP面试考察范围. 有需要联系:QQ:1844912514

  9. Iris jwt 使用

    jwt分为三个部分: ​ 1.header,用来存储算法和token类型等信息 ​ 2.payload, 一些简单的信息 ​ 3.签名,来验证token是否合法 iris-jwt 这是初始化jwt中间 ...

  10. C&num;获取当前堆栈的各调用方法列表

    在使用.NET编写的代码在debug时很容易进行排查和定位问题,一旦项目上线并出现问题的话那么只能依靠系统日志来进行问题排查和定位,但当项目复杂时,即各种方法间相互调用将导致要获取具体的出错方法或调用 ...