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://www.clanfei.com/2012/04/605.html
欢迎访问交流,至于我为什么要多弄一个博客,因为我热爱前端,热爱网页,我更希望有一个更加自由、真正属于我自己的小站,或许并不是那么有名气,但至少能够让我为了它而加倍努力。。
=======================签 名 档=======================
分享到:
相关推荐
The 2014 ACM-ICPC Asia Beijing Regional Contest
湖南师大数计院ACM—ICPC个人邀请赛题目及解答,非常的不错哦,详细的代码和解题报告,题目有的很巧妙,这套题目比较重数学~~
用蛮力法解决的Acm icpc试题(求矩阵每一列列和的最小值)。
一些例程--ACM/ICPC简单程序 竞赛训练用
ACM-ICPC asia phuket problem
Algorithm-ACM_ICPC_Materials.zip,acm-icpc的制备材料,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
ACM__ICPC__重要补充知识.doc
背包九讲2.0_算法_动态规划_ACM_
2013 ACM_ICPC 南京赛区网络赛题目
ACM_ICPC在线评测系统_OJ,教你实现评测的过程
数据结构算法与应用-C__语言描述及ACM/ICPC讲解;
ACM_算法模板集史上最完整收藏版223页全免费版.pd
ACM_ICPC ACM_ICPC源代码
杭电hdu acm资料所用杭电的acm题
浙江大学ACM题解JU_ACM_All_Anwer,里面一本非常好的chm电子书,浙大的所有ACM题及题解都在了,对学习ACM的朋友非常的好~还等什么呢?
acm,动态规划类问题分析,并附有这些问题的详细代码
动态规划相关的,用最开始的背包问题开始讲起,然后进行各种延申,帮助人理解动态规划
2010年ACM/ICPC暑期集训的时候自己做的组合数学讲稿,希望能多大家的授课有所帮助~~ 目录 1 引言 组合数学 1 1.1 组合数学研究的基本问题 1 1.2 两个基本计数原理 1 1.2.1 加法原理 1 1.2.2 乘法原理 1 1.3 排列...