cug oj 1479 Treasure Chest Lock （区间dp 思维）

1479: Treasure Chest Lock

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 7 Solved: 5
[Submit][Status][Web Board]

Description

Vic has a treasure chest. And there is a lock on the treasure chest. The lock contains a sequence of wheels. Each wheel has the 26 letters of the English alphabet

‘a’ through ‘z’, in order. If you move a wheel up, the letter it shows changes to the next letter in the English alphabet (if it was showing the last letter ‘z’, then it

changes to ‘a’). If you move the wheel down, it changes to show the previous letter in the English alphabet (if it was showing ‘a’, then it changes to ‘z’).

It is also possible to move any subsequence of contiguous wheels in the same direction with only one movement. This has the same effect of moving each of the

wheels within the subsequence on that direction, but saves the effort of doing that one wheel at a time.The lock openswhen the wheels show a secret sequence of l

etters. Currently all wheels are showing the letter ‘a’. Vic wants to know the minimum number of movements you need to open the lock.

Input

The input has several test cases. Each of them is given in exactly one line containing a nonempty string of at most 1000 lowercase letters. The string represents

the secret sequence of letters that opens the lock.

Output

For each test case, output a line containing a single integer with the minimum number of movements to open the lock.

Sample Input

abcxyz

abcdefghijklmnopqrstuvwxyz

aaaaaaaaa

zzzzzzzzz

zzzzbzzzz

Sample Output

525013

题意：

给你一个字符串，每次能够选择一个子串ss，将ss总体+1或者总体-1，a+1=b,a+1=a。要将全部字符全变为a，问最小的步数。

思路：

能够想到两种属性相反的操作（一加一减）不可能重叠，假设重叠的话。能够改动它们到不重叠也达到同样的效果。然后每一个字符就是通过一系列'+'操作或者‘-’操作（仅仅能选其1）得到a的。可是能够+或者-非常多次，不信能够看这个样例。mtezqh。答案为30.

dn[i][j]表示到将前i个字符所有变为a，最后一个字符‘-’j圈（假设j=0，仅仅需操作s[j]-'a'次）最小步数。

up[i][j]表示到将前i个字符所有变为a，最后一个字符‘+’j圈（假设j=0。仅仅需操作‘a+'26-s[j]-次）最小步数。

然后递推就可以。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#define maxn 1005
#define MAXN 200005
#define INF 0x3f3f3f3f
#define mod 20140518
#define eps 1e-6
const double pi=acos(-1.0);
typedef long long ll;
using namespace std;

int n,m;
int up[maxn][40],dn[maxn][40];
char s[maxn];

void solve()
{
    int i,j,k;
    n=strlen(s+1);
    memset(dn,0x3f,sizeof(dn));
    memset(up,0x3f,sizeof(up));
    dn[1][0]=s[1]-'a';
    up[1][0]='a'+26-s[1];
    for(i=1; i<n; i++)
    {
        for(j=0; j<30; j++)
        {
            if(s[i+1]==s[i])
            {
                dn[i+1][j]=dn[i][j];
                up[i+1][j]=up[i][j];
            }
            else if(s[i+1]<s[i])
            {
                if(dn[i][j]<INF)
                {
                    dn[i+1][j]=min(dn[i+1][j],dn[i][j]);
                    if(j>0) dn[i+1][j-1]=min(dn[i+1][j-1],dn[i][j]);
                    dn[i+1][j+1]=min(dn[i+1][j+1],dn[i][j]+s[i+1]-s[i]+26);
                    up[i+1][0]=min(up[i+1][0],dn[i][j]+'a'+26-s[i+1]);
                }
                if(up[i][j]<INF)
                {
                    up[i+1][j]=min(up[i+1][j],up[i][j]+s[i]-s[i+1]);
                    if(j>0) up[i+1][j-1]=min(up[i+1][j-1],up[i][j]);
                    up[i+1][j+1]=min(up[i+1][j+1],up[i][j]+s[i]-s[i+1]+26);
                    dn[i+1][0]=min(dn[i+1][0],up[i][j]+s[i+1]-'a');
                }
            }
            else
            {
                if(dn[i][j]<INF)
                {
                    dn[i+1][j]=min(dn[i+1][j],dn[i][j]+s[i+1]-s[i]);
                    if(j>0) dn[i+1][j-1]=min(dn[i+1][j-1],dn[i][j]);
                    dn[i+1][j+1]=min(dn[i+1][j+1],dn[i][j]+s[i+1]-s[i]+26);
                    up[i+1][0]=min(up[i+1][0],dn[i][j]+'a'+26-s[i+1]);
                }
                if(up[i][j]<INF)
                {
                    up[i+1][j]=min(up[i+1][j],up[i][j]);
                    if(j>0) up[i+1][j-1]=min(up[i+1][j-1],up[i][j]);
                    up[i+1][j+1]=min(up[i+1][j+1],up[i][j]+s[i]-s[i+1]+26);
                    dn[i+1][0]=min(dn[i+1][0],up[i][j]+s[i+1]-'a');
                }
            }
        }
    }
    int ans=min(dn[n][0],up[n][0]);
    printf("%d
",ans);
}
int main()
{
    while(~scanf("%s",s+1))
    {
        if(s[1]=='*') break ;
        solve();
    }
    return 0;
}
/*
mtezqh
ans 30 e -26-e
*/

525013