给定一个长度为N的字符串S和一个正整数K，将S划分为K个非空子串，使得子串长度的平方和最大。例如：S=“abcd”，K=2，可以将S划分为“ab”和“cd”，和为2^2 + 2^2 = 8，还可以将S划分为“a” 和 “bcd”,和为 1^2 + 3^2 = 10.，后者更大，所以答案为10.求C语言

这个问题可以使用动态规划来解决。我们可以定义一个状态$f(i, j)$表示将前$i$个字符划分为$j$个非空子串时子串长度的平方和的最大值。假设第$j$个子串的结束位置为$k$，则状态转移方程为：

$$
f(i, j) = \max_{k=1}^{i} \{f(k, j-1) + (i-k+1)^2\}
$$

其中，$1 \leq k \leq i$，$j \geq 1$。这个方程的意思是，我们枚举最后一个子串的结束位置$k$，将前$k$个字符划分为$j-1$个非空子串，然后将第$j$个子串划分为$k+1$到$i$之间的字符，这样可以保证第$j$个子串非空。状态转移方程的含义是，将前$i$个字符划分为$j$个非空子串的最大平方和，等于将前$k$个字符划分为$j-1$个非空子串的最大平方和，加上第$j$个子串的平方长度$(i-k+1)^2$。

最终的答案为$f(N, K)$。由于状态转移方程中需要枚举$k$，时间复杂度为$O(N^2K)$。

以下是使用动态规划求解字符串划分问题的C语言代码示例：

#include <stdio.h>
#include <string.h>

#define MAX_N 1000
#define MAX_K 100

int n, k;
char s[MAX_N+1];
int dp[MAX_N+1][MAX_K+1];  // 状态数组

// 计算前i个字符划分为j个非空子串时子串长度的平方和的最大值
int solve() {
    memset(dp, 0, sizeof(dp));  // 初始化状态数组
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            dp[i][j] = -1;  // 初始化为-1
            for (int p = 1; p <= i; p++) {
                if (dp[p-1][j-1] >= 0) {  // 如果前p-1个字符可以划分为j-1个非空子串
                    int sum = 0;
                    for (int q = p; q <= i; q++) {
                        sum += (s[q] - 'a' + 1) * (s[q] - 'a' + 1);  // 计算第j个子串的长度平方和
                    }
                    if (dp[i][j] == -1 || dp[p-1][j-1] + sum < dp[i][j]) {
                        dp[i][j] = dp[p-1][j-1] + sum;  // 更新状态
                    }
                }
            }
        }
    }
    return dp[n][k];
}

int main() {
    scanf("%d %d %s", &n, &k, s+1);
    int res = solve();
    printf("%d\n", res);
    return 0;
}

此代码使用了一些技巧来减少状态转移方程中的循环次数，时间复杂度为$O(N^2K)$。