秘密代码

题目

对于一个字符串S只由大写字母组成 通过一系列操作对其进行加密操作为删除S的前面或者后面的若干个字符(但不删光整个S),并将剩下的部分连接到原字符串S的前面或者后面给出加密后的字符串 问共有几种加密方法?

输入输出格式

输入格式

一个字符串S (len<=100)

输出格式

几种加密方法

思路

由于长度较小可以使用暴力预处理字符的相同部分
f[i][j][k] 表示从i位置往后k个单位长度和从j位置往后k个单位长度是否相同

用dp思想进行区间动规 枚举删去后留下的长度进行更新


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <cmath>
using namespace std;
const int mod = 2014;
int dp[120][120];
char a[105];
int f[120][120][120];
int len;
int main()
{
scanf("%s", (a + 1));
len = strlen(a + 1);
for (int i=1; i<=len; i++)
for (int j=1; j<=len; j++)
for (int k=1; i+k-1<=len && j+k-1<=len && a[i+k-1]==a[j+k-1]; k++)
f[i][j][k] = 1;
for (int i=1; i<=len; i++)
for (int j=1; j<=len; j++)
dp[i][j] = 1;
for (int w=2; w<=len; w++)// 要更新串的长度
for (int i=1; i+w-1<=len; i++)// 要更新串的开头位置
{
int j = i + w - 1;// 要跟新串的结尾位置
for (int k=1; k*2<w; k++)// 删除后留下K的长度
{
if (f[i][i+k][k]) dp[i][j] += dp[i+k][j], dp[i][j] %= mod;
// 表示要更新串是由i+k~j的长度删去末尾几个字符后加到原串的开头得到
if (f[i][j-k+1][k]) dp[i][j] += dp[i+k][j], dp[i][j] %= mod;
// 表示要更新的串是由i+k~j的长度删去开头几个字符后加到原串的开头得到
if (f[i][j-k+1][k]) dp[i][j] += dp[i][j-k], dp[i][j] %= mod;
// 表示要更新的串是由i~j-k的长度删去末尾几个字符后加到原串的末尾得到
if (f[j-2*k+1][j-k+1][k]) dp[i][j] += dp[i][j-k], dp[i][j] %= mod;
// 表示要更新的串是由i~j-k的长度删去开头几个字符后加到原串的末尾得到
}
}
printf("%d\n", dp[1][len] - 1);
return 0;
}