题目内容

如果一个字符串$s$可以由某个字符串$t$重复$x(x>1)$次得到，就称字符串$s$为一个真周期串。

例如：$s=01230123,t=0123,x=2$。对于一个只包含数字$0$ ~ $9$的字符串$S$，可以执行任意次（也可以不执行）操作，选择任意两个下标，交换两个下标的字符。更正式地说，选择$i,j(i≠j)$交换$S_i$和$S_j$。如果字符串$S$经过操作后可以变成真周期串，那么称$S$为伪周期串。现在给定一个只包含数字$0$~$9$的字符串$T$，问：最多可以将字符串$T$划分成几个伪周期串？更正式地说，找出一个大小为$k$的伪周期串集合$P$，使得$T=P_1+P_2+…+P_k$输出最大的$k$。

思路

  此题也是一个较为经典的动态规划类型，整体意思就是要将原字符串分割为几块，每一块都是一个伪周期串，要求最多能分成多少块，设dp[i]为字符串以i为结尾最多能分出多少，转移则是枚举结尾是i的所有伪周期串，对伪周期串之前的字符串进行转移，判断是否为为周期串的条件即为出现的每一种字母数量总最大公约数大于1

代码

java

import java.util.Scanner;

public class Main {
    public static int gcd(int a, int b) {