sdut 无尽走廊 – 源码巴士

无尽走廊

Time Limit: 1000MS Memory limit: 65536K

题目描述

    2006年，我们可以称之为“帆“船年。一艘艘友谊的小船都在这一年翻掉了(当然也有升华为巨轮的)。然而这种事注定与小鱼无缘，就在不久前，小鱼与小驴刚吵了一架，在争吵的过程中，小鱼与小驴友谊的小木船失衡翻掉了。小鱼与小驴坠入大海，小鱼醒来后发现小驴不见了，慌张的小鱼四处寻找小驴，但小鱼发现小驴并不在小鱼身边。此时小鱼发现自己在一个大大的走廊尽头，走廊那边是无尽的黑暗，而小鱼身旁的一个告示牌上有如下内容:
    亲爱的人类啊～欢迎来到海洋之邸～想要找到你的朋友么～那就穿越这条无尽走廊吧～下面有一张魔法地图～可以带你通向海底堡～你的朋友就在那里等着你那～下面有一张魔法地图～可以带你离开这里～
    小鱼捡起地图，发现这条走廊是由好几条小走廊组成，地图上每条小走廊由一个大写英文字母表示。而小鱼现在在第一个字母处，出口在最后一个字母。
    地图上说，每个小走廊都有一扇时空之门，可以跳转到当前走廊往后第1~k个走廊处。而所需要的时间为两走廊字母编号的距离。譬如A走廊与B走廊间花费为1 Z与A花费为25 C与A花费为2。
    小鱼现在十分后悔跟小驴吵架。急切地想要找到小驴，你能帮小鱼算出一种方案，能够尽快找到小驴么?

输入

多组输入。
先输入一个整数T，表示组数。
之后每组先输入一个字符串(0 < 串长 <= 10^4)，之后输入一个整数k(1 <= k <= 串长)表示每次最远移动距离。
每组输入占一行，以空格隔开。

输出

对于每组输入，输出一个正整数表示小鱼找到小驴的最短时间。每组输出占一行。

示例输入

3
ACA 1
ACA 2
ABCA 2

示例输出

4
0
2

提示

对于第二组输入，在第一个走廊处往后移动两步，到达尽头。
对于第三组输入，在第一个走廊处先移动一步到达第二个走廊，再移动两步到达尽头，时间最短。

来源

“师创杯”山东理工大学第八届ACM程序设计竞赛

示例程序

提交
状态

分析题意我们可以知道对于当前点pos的最优决策来至 pos-k~pos-1之中由于一共就26个字母，我们可以维护这26个字母在不同区间是否可达和其最优解，利用multiset就可以搞一搞了

ACcode：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 10002
#include <set>
using namespace std;
char str[maxn];
int sum[maxn];
int dp[maxn];
int loop,k,len;
int main(){
    scanf("%d",&loop);
    while(loop--){
        scanf("%s%d",str+1,&k);
        len=strlen(str+1);
        for(int i=1;i<=len;++i)sum[i]=str[i]-'A';
        memset(dp,0,sizeof(dp));
        multiset <int> q[26];
        q[str[1]-'A'].insert(0);
        for(int i=2;i<=len;++i){
            int ans=0x3f3f3f3f;
            for(int j=0;j<26;++j)
                if(!q[j].empty())
                    ans=min(ans,*(q[j].begin())+abs(sum[i]-j));
            dp[i]=ans;
            if(i>k)
                q[sum[i-k]].erase(q[sum[i-k]].find(dp[i-k]));
            q[sum[i]].insert(dp[i]);
        }
        printf("%d\n",dp[len]);
    }
    return 0;
}


/**************************************
	Problem id	: SDUT OJ E 
	User name	: acmer 
	Result		: Accepted 
	Take Memory	: 1056K 
	Take Time	: 230MS 
	Submit Time	: 2016-06-01 23:33:46  
**************************************/

原文链接：https://blog.csdn.net/zp___waj/article/details/51577935