[ACM_ZJUT_1021]ACMICPC(暴力破解VS动态规划)

蓝飞 蓝飞 | 时间:2012-04-09, Mon | 9,142 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;
}

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

ACMICPC

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

如需转载请注明出处:蓝飞技术部落格

当前暂无评论 »