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

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暴力破解中，动态规划完胜！ [鼓掌]

=======================签 名 档=======================
原文地址（我的博客）：http://lanfei.sinaapp.com/2012/04/605.html
欢迎访问交流，至于我为什么要多弄一个博客，因为我热爱前端，热爱网页，我更希望有一个更加自由、真正属于我自己的小站，或许并不是那么有名气，但至少能够让我为了它而加倍努力。。
=======================签 名 档=======================