给定一个长度为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.输入第一行包含 N and K (1 <= K <= N <= 1000), 输入第二行包含字符串S，均为小写。输出一行一个整数，表示最大和.c语言或c++,动态规划法

以下是C++代码实现动态规划法解决该问题：

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

const int MAXN = 1005;
const int INF = 1e9;
int n, k, a[MAXN];
long long dp[MAXN][MAXN];

int main() {
    cin >> n >> k;
    string s;
    cin >> s;
    for(int i = 0; i < n; i++) {
        a[i+1] = s[i] - 'a' + 1; // 将小写字母转化为1~26的数字表示
    }
    memset(dp, 0x3f, sizeof(dp)); // 初始化dp数组为INF
    dp[0][0] = 0;
    for(int i = 1; i <= n; i++) {
        dp[i][1] = 0; // 将前i个字符划分为1段，和为0
        for(int j = 2; j <= min(i, k); j++) {
            int sum = 0;
            for(int p = i; p >= j; p--) {
                sum += a[p];
                dp[i][j] = min(dp[i][j], dp[p-1][j-1] + sum * sum);
            }
        }
    }
    cout << dp[n][k] << endl;
    return 0;
}

算法思路：

定义状态dp[i][j]表示前i个字符划分为j个非空子串，使得子串长度的平方和最大。

对于每个状态dp[i][j]，我们可以枚举最后一段子串的起点p，那么前p-1个字符就被划分为了j-1段，且最后一段子串的和为a[p]+a[p+1]+...+a[i]，那么状态转移方程如下：

dp[i][j] = min(dp[i][j], dp[p-1][j-1] + (a[p]+a[p+1]+...+a[i])^2)

最后的答案即为dp[n][k]。

时间复杂度为O(n^3)。