ACMICPC
Time Limit:1000MS Memory Limit:32768K
Description:
大写字母A-Z分别对应整数[-13,12]，因此，一个字符串对应了一个整数列。我们把字符串对应的整数列的和称为该字符串的特性值。例如：字符串ACM对应的整数列为{-13,-11,-1}，则ACM的特性值为(-13)+(-11)+(-1)=-25；其子串AC的特性值为-24；子串M的特性值为-1。给你一个字符串，请找出该字符串的所有子串的最大特性值。
Input:
第一行的正整数 N（1<=N<=1000）表示其后有N组测试数据，每组测试数据都由一个字符串组成。字符串只能由大写字母A-Z组成，且字符串的长度不会超过1000。
Output:
输出有N行，每行是一组测试数据的输出结果。
Sample Input:
2 ACM ANGRY
Sample Output:
-1 15
http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1021
/* --------------------------------------------------------------------------------
非动态规划解法：
做法：遍历所有字串，找出最大那个。
时间：297MS
内存：196K
-------------------------------------------------------------------------------- */
#include<stdio.h>
char szStr[1004] ;
int a[1004] ;
int main(void)
{
int i = 0 ;
int j = 0 ;
int t = 0 ;
int n = 0 ;
int nMax = -1000 ;
scanf("%d",&t) ;
getchar() ;
while(t-- > 0)
{
gets(szStr) ;
nMax = -1000 ;
j = 1 ;
i = 0 ;
while(szStr[i] != '\0')
{
a[j++] = szStr[i] - 65 - 13 ;
i++ ;
}
n = j - 1 ;
a[0] = 0 ;
for(i = 1 ; i <= n ; ++i)
{
if(a[i] >= nMax)
{
nMax = a[i] ;
}
a[i] += a[i-1] ;
if(a[i] >= nMax)
{
nMax = a[i] ;
}
for(j = 1 ; j < i ; ++j )
{
if(a[i] - a[j] >= nMax)
{
nMax = a[i] - a[j] ;
}
}
}
printf("%d\n",nMax) ;
}
return 0 ;
}
/* －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
动态规划解法：
时间：9MS
内存：200K
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ */
#include<stdio.h>
#define max(x,y) ((x)>(y) ? (x) : (y))
char szStr[1004] ;
int a[1004] ;
int b[1004] ;
int main(void)
{
int i = 0 ;
int j = 0 ;
int t = 0 ;
int n = 0 ;
int nMax = -1000 ;
scanf("%d",&t) ;
getchar() ;
while(t-- > 0)
{
gets(szStr) ;
nMax = -1000 ;
j = 1 ;
i = 0 ;
while(szStr[i] != '\0')
{
a[j++] = szStr[i] - 65 - 13 ;
i++ ;
}
n = j - 1 ;
b[0] = -1000 ;
nMax = -1000 ;
for(i = 1 ; i <= n ; ++i)
{
b[i] = max(a[i],b[i-1]+a[i]) ;
if(nMax < b[i])
{
nMax = b[i] ;
}
}
printf("%d\n",nMax) ;
}
return 0 ;
}
/* --------------------------------------------------------------------------------------
动态规划解法：
不过，优化了时间和空间复杂度。在时间方面边输入边处理，所以只是遍历一次。
在空间方面因为是边输入边处理，所以不用字符串来保存。
时间：7MS
内存：196K
-------------------------------------------------------------------------------------- */
#include<stdio.h>
#define max(x,y) ((x)>(y) ? (x) : (y))
int b[1004] ;
int main(void)
{
int i = 0 ;
int j = 0 ;
int t = 0 ;
int n = 0 ;
int nMax = -1000 ;
int nTemp = 0 ;
char chCur = '\0' ;
scanf("%d",&t) ;
getchar() ;
while(t-- > 0)
{
nMax = -1000 ;
b[0] = -1000 ;
i = 1 ;
while((chCur = getchar()) != '\n')
{
nTemp = chCur - 65 - 13 ;
b[i] = max(nTemp,b[i-1]+nTemp) ;
if(nMax < b[i])
{
nMax = b[i] ;
}
i++ ;
}
printf("%d\n",nMax) ;
}
return 0 ;
}