[ACM_ZJUT_1021]ACMICPC（暴力破解VS动态规划）

杰拉斯 | 时间：2012-04-09, Mon | 17,964 views
编程算法　

ACMICPC

Time Limit:1000MS Memory Limit:32768K
Description:

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

Source

ZJUT1021

今天@王xiao瓶童鞋问了我这么一道题，她做出来的结果跟示例完全一样，其它测试结果也没有问题，可是却出现了纠结的TLE：

#include<iostream>
#include<string>
using namespace std;
int main()
{
	int best;
	string str="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		string s;
		cin>>s;
		best=-13;
		for(int j=0;j<s.size();j++)
		{
			int sum=0;
			for(int k=j;k<s.size();k++)
			{
				int temp = str.find(s[k]);
				sum += (temp-13);
				if(sum>best)
					best = sum;
			}
		}
		cout <<best<<endl;
	}
	return 0;
}

这究竟是为什么呢？我很纠结地看到了int temp = str.find(s[k]);这句语句，要知道find的效率是很低的，而且这句语句完全可以用int temp = s[k] - 'A';来代替。马上改了一下，果然立马就Accpet了：

#include<iostream>
#include<string>
using namespace std;
int main()
{
	int best;
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		string s;
		cin>>s;
		best=-13;
		for(int j=0;j<s.size();j++)
		{
			int sum=0;
			for(int k=j;k<s.size();k++)
			{
				int temp = s[k] - 'A';
				sum += (temp-13);
				if(sum>best)
					best = sum;
			}
		}
		cout <<best<<endl;
	}
	return 0;
}

于是我想，暴力破解的效率还是很低，能不能用最近刚了解的动态规划来实现呢？写了一下，果然可以通过：

#include<stdio.h>
#include<string>
#include<algorithm>
using namespace std;
int main(){
	int n, f[1000];
	char s[1000];
	scanf("%d", &n);
	while(n--){
		int ans;
		scanf("%s", &s[0]);
		for(int i = 0; i < strlen(s); ++i){
			f[i] = s[i] - 'A' - 13;
		}
		ans = f[0];
		for(int i = 1; i < strlen(s); ++i){
			f[i] = max(f[i], f[i - 1] + f[i]);
			if(f[i] > ans)
				ans = f[i];
		}
		printf("%d\n", ans);
	}
	return 0;
}

当然，这段代码看起来虽然比较容易懂了，但明显还是不够简洁，于是在追求完美精神的鼓舞下和@蜗牛都知道的怂恿下，优化了一下：

#include<stdio.h>
#include<string>
#include<algorithm>
using namespace std;
int main(){
	int n, f[1000];
	char s[1000];
	scanf("%d", &n);
	while(n--){
		int ans;
		scanf("%s", &s[0]);
		ans = f[0] = s[0] - 'A' - 13;
		for(int i = 1; i < strlen(s); ++i){
			f[i] = s[i] - 'A' - 13;
			f[i] = max(f[i], f[i - 1] + f[i]);
			if(f[i] > ans)
				ans = f[i];
		}
		printf("%d\n", ans);
	}
	return 0;
}

下面分别是三段代码的提交状况：

很明显，动态规划VS暴力破解中，动态规划完胜！ [鼓掌]

如需转载请注明出处：杰拉斯的博客

杰拉斯的博客