uva11258- String Partition(遞推)

uva11258- String Partition(遞推)

題目：uva11258- String Partition(遞推)

題目大意：給出一系列的數字，它是由很多int型的數構成的，就是中間沒有加空格。所以現在問怎樣拆分這些數，使得這些數之和最大。

解題思路：這裡要求是int型的整數，單個數的最大的值2147483647.dp【i】【j】代表這個數字串第i個字符到第j個字符能夠得到的最大的和。

dp【i】【j】 = max（dp【i】【i + k】 + dp【i + k + 1】【j】） k >= 0 && k <= j - i - 1. 因為可能最後的這個j和前面的n個字符構成整數能夠得到更大的值。

例如 ： 12345678910 這個數可能的劃分 1| 345678912 , 12| 345678910 ,123| 45678910, 1234|5678910, 12345 | 678910, 123456|78910， 1234567|8910， 12345678|910， 123456789|10， 1234567891|0這10種劃分。第一種劃分是因為|後面的那個數已經超過最大值了，所以需要再劃分成兩個數。還有一種可能就是這個數它的長度小於10,那麼這個數當然不劃分最大了。如果等於10 的話，就需要看值會不會超過最大值，如果超過就需要劃分。

代碼：

#include 
#include 

typedef long long ll;

const int N = 205;
const ll maxn = 2147483647;

ll dp[N][N];
char str[N];
char s1[N];
char s2[N];
int len;

ll Max (const ll a, const ll b) { return a > b ? a : b; }

ll MaxNum (int j, int l) {

	ll ans;
	memcpy (s1, str + j, sizeof (char) * (l + 1));
	s1[l + 1] = '\0';
	sscanf (s1, "%lld", &ans);
	/*if (ans > maxn) {

		memcpy (s1, str + j + 1, sizeof (str + j + 1));
		s1[j + l] += str[j];
		s1[j + l  + 1] = '\0';
		memcpy (s2, str + j, sizeof (str + j));
		s2[j + l - 1] += str[j + l];
		s2[j + l] = '\0';

		if (strcmp (s1, s2) > 0)
			sscanf (s1, "%lld", &ans);
		else
			sscanf (s2, "%lld", &ans);
	}*/
	if (ans > maxn)
		return -1;
	return ans;
}

void init () {

	for (int i = 0; i < len; i++) 
		dp[i][i] = str[i] - '0'; 				
}

int main () { 

	int t;
	ll ans;
	ll temp;
	scanf ("%d", &t);
	while (t--) {

		scanf ("%s", str);

		len = strlen (str);

		if (len < 10) 	
			sscanf (str, "%lld", &ans);
		else {

			init();
//			printf ("%lld\n", MaxNum (0, 9));
			for (int l = 1; l < len; l++)
				for (int i = 0; i + l < len; i++) {

					temp = -1;
					if (l < 10) 
						temp = MaxNum(i, l);
					for (int k = 0; k < l; k++) 			
						temp = Max (temp, dp[i][i + k] + dp[i + k + 1][i + l]);
					dp[i][i + l] = temp;
				}

			ans = dp[0][len - 1];
		}

		printf ("%lld\n", ans);
	}
	return 0;
}