Codeforces 825F String Compression 字符串,dp

这可能将是我oi生涯切的最后一道题了.
oi,有缘再见.

我和你 要怎样的时机
才可以 在期待中相遇
这一刻的心境 若凝结成言语
将为你记叙 一路沿途的风景
我与你是命中注定 是交错的命运
与你的一切联系 是神的旨意
我与你是一心同体 是必然定律
可是我爱你 绝对不只是神传递的指令
$\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad\qquad \qquad-$−《神谕法则》

题意

$可以将一个字符串中连续重复的字符串压成出现次数加该字符串的形式,比如说\newline abababab压成4ab,aaaaaaaaaa压成10a,求给定字符串最短压缩的长度.$可以将一个字符串中连续重复的字符串压成出现次数加该字符串的形式,比如说abababab压成4ab,aaaaaaaaaa压成10a,求给定字符串最短压缩的长度.

题解

考虑$dp$dp.
定义$dp_i$dpi​为字符串的前$i$i位压缩的最短长度.
我们从$dp_i$dpi​转移到$dp_{j-1}$dpj−1​,朴素的话要$O(n)$O(n)转移.
我们考虑预处理$1\to n$1→n在十进制下的位数和$i,j$i,j开始最多能够匹配多少位.
可以分别$O(n)$O(n)和$O(n^2)$O(n2)预处理.

for (i=1;i<=n;++i) lg[i]=lg[i/10]+1;
for (i=n;i;--i) {
  for (j=n;j;--j) {
    pre[i][j]=s[i]==s[j]?pre[i+1][j+1]+1:0;  
  }
}

接下来开始转移.
对于区间$[i,j]$[i,j]这一个子串,考虑$p=i$p=i位置先开始转移.
如果$i,p$i,p两个位置匹配的长度大于或者等于$[i,j]$[i,j]长,我们就可以把$dp[i-1]$dp[i−1]的答案转移到$dp[p+j-i]$dp[p+j−i].
转移的方程就是$dp[i-1]+(j-i+1)+lg[times]$dp[i−1]+(j−i+1)+lg[times],$times$times是连续匹配$[i,j]$[i,j]的次数.
最后输出$dp_n$dpn​即可.
谢谢大家.

#include<bits/stdc++.h> //Ithea Myse Valgulious
namespace chtholly{
typedef long long ll;
#define re0 register int
#define rel register ll
#define rec register char
#define gc getchar
//#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?-1:*p1++)
#define pc putchar
#define p32 pc(' ')
#define pl puts("")
/*By Citrus*/
char buf[1<<23],*p1=buf,*p2=buf;
inline int read(){
  int x=0,f=1;char c=gc();
  for (;!isdigit(c);c=gc()) f^=c=='-';
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return f?x:-x;
  }
template <typename mitsuha>
inline bool read(mitsuha &x){
  x=0;int f=1;char c=gc();
  for (;!isdigit(c)&&~c;c=gc()) f^=c=='-';
  if (!~c) return 0;
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return x=f?x:-x,1;
  }
template <typename mitsuha>
inline int write(mitsuha x){
  if (!x) return 0&pc(48);
  if (x<0) pc('-'),x=-x;
  int bit[20],i,p=0;
  for (;x;x/=10) bit[++p]=x%10;
  for (i=p;i;--i) pc(bit[i]+48);
  return 0;
  }
inline char fuhao(){
  char c=gc();
  for (;isspace(c);c=gc());
  return c;
  }
}using namespace chtholly;
using namespace std;
const int aoi=8015; 
typedef int you[aoi];
char s[aoi]; 
you lg,dp,pre[aoi],tmp;
int main() {
  scanf("%s",s+1);
  int i,j,k,n=strlen(s+1);
  for (i=1;i<=n;++i) lg[i]=lg[i/10]+1; // 预处理i是几位数.
  for (i=n;i;--i) {
    for (j=n;j;--j) {
      pre[i][j]=s[i]==s[j]?pre[i+1][j+1]+1:0;
    }
  }
  /*pre[i][j]表示从i,j开始匹配子串最多能够匹配多少位.*/
  fill(dp+1,dp+n+1,oi);
  for (i=1;i<=n;++i) {
    memset(tmp,0,sizeof tmp);
    /*标记数组*/
    for (j=i;j<=n;++j) if (!tmp[j]) { 
      int net=j-i+1,t=0,p=i; 
      for (;pre[i][p]>=net;) { // 从p开始能够匹配整个[i,j]子串
        tmp[(p+=net)-1]=1; // 标记p+len-1位置,因为p开始至少能够匹配一遍[i,j]子串.
        dp[p-1]=min(dp[p-1],dp[i-1]+net+lg[++t]); // i-1的答案传到p-1,加上当前子串长度,次数+1.
      } 
    }
  }
  write(dp[n]);
}
/*
aaaaaaaaaaa
*/