ACM－ACMICPC (AC，动态规划/遍历所有字串，三份代码)

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 ;
}