uva 11258 - String Partition（dp)

本文主要是介绍uva 11258 - String Partition（dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接： 11258 - String Partition

题目大意：给出一个字符串，由0~9组成，现在可以将字符串切割成若干段，每一段便可代表一个数值，但是这个数值不能大于int的最大上限，问，如何切割可以使得这若干个数的和最大。

解题思路：一开始想用区间dp做，但是小伙伴告诉我可以用递推的方法，就去找了一下代码，确实非常简单,dp[i]表示第i位数以前的最优解，由于int型数最多10位数，所以就可以枚举位数求解，具体在代码里面。

#include <stdio.h>
#include <string.h>
#include <limits.h>
const int N = 205;
long long dp[N];
int n;
char str[N];
long long max(long long a, long long b) { return a > b ? a : b; }void solve() {n = strlen(str);memset(dp, 0, sizeof(dp));for (int i = 1; i <= n; i++) {for (int j = 1; j <= 10 && j <= i; j++) {long long sum = 0;for (int k = 0; k < j; k++) {sum = sum * 10 + str[i - j + k] - '0';if (sum >= 0 && sum <= INT_MAX)dp[i] = max(dp[i], dp[i - j] + sum);elsebreak;}}}
}int main() {int cas;scanf("%d%*c", &cas);while (cas--) {gets(str);solve();printf("%lld\n", dp[n]);}return 0;
}

这篇关于uva 11258 - String Partition（dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---