Codeforces Beta Round #96 (Div. 1) C. Logo Turtle —— DP

题目链接：http://codeforces.com/contest/132/problem/C

 

C. Logo Turtle

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

A lot of people associate Logo programming language with turtle graphics. In this case the turtle moves along the straight line and accepts commands "T" ("turn around") and "F" ("move 1 unit forward").

You are given a list of commands that will be given to the turtle. You have to change exactly n commands from the list (one command can be changed several times). How far from the starting point can the turtle move after it follows all the commands of the modified list?

Input

The first line of input contains a string commands — the original list of commands. The string commands contains between 1 and 100 characters, inclusive, and contains only characters "T" and "F".

The second line contains an integer n (1 ≤ n ≤ 50) — the number of commands you have to change in the list.

Output

Output the maximum distance from the starting point to the ending point of the turtle's path. The ending point of the turtle's path is turtle's coordinate after it follows all the commands of the modified list.

Examples

input

FT
1

output

2

input

FFFTFFF
2

output

6

Note

In the first example the best option is to change the second command ("T") to "F" — this way the turtle will cover a distance of 2 units.

In the second example you have to change two commands. One of the ways to cover maximal distance of 6 units is to change the fourth command and first or last one.

 

 

 

题解：

方法一（四维dp）：

1.dp[i][j][dir][dis]表示：执行到第i个指令，修改了j个指令，前进方向为dir，且到达了dis的地方的情况是否存在。其值为0或1。

2.枚举已有状态，推出下一步状态。（与常见的dp不同，常见的dp为枚举可能的状态，然后看他能从那些状态转移过来）。

3.由于结束点可能在左边，即距离为负数，为了防止溢出，将起始点往右移100。

类似的做法的题：http://blog.csdn.net/dolfamingo/article/details/73903530

易错点：

写成dp[i][j][dir][dis] 或者dp[i][j][dis][dir]都可以，但是写成dp[dir][i][j][dis] 或者dp[dis][i][j][dir]等等就不行了，因为枚举的顺序不对。递推必须自底向上，如果“底”都没推出来，那“上”自然也推不出来了。

学习之处：

一：目前了解到的递推式DP有两种：

1.当前状态（可能不存在）能从哪些状态转移过来。 被赋值的状态是当前状态。

 2.当前状态（已存在）能推出哪些状态。 被赋值的状态是被推出来的状态。

二：

当设定的k维dp不好递推时，如果再加多一维（这一维是数值，且范围很小）仍不会超时，那么就可以改写成k+1维的dp，这样所有可能的状态都通过dp数组的下标体现出来了，所以要做的就是：递推出存在的状态，然后在这些状态中找出最优结果。

 

四维DP：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double eps = 1e-6;
const int INF = 2e9;
const LL LNF = 9e18;
const int mod = 1e9+7;
const int maxn = 100+10;

int n, m, dp[110][55][2][210];
char s[maxn];

void init()
{
    scanf("%s%d",s+1, &m);
    n = strlen(s+1);

    dp[0][0][0][100] = 1;    //起始点平移到100，防止下标溢出
    for(int i = 0; i<n; i++)
    for(int j = 0; j<=m; j++)  //这样枚举，一个指令最多只能修改一次
    for(int dir = 0; dir<2; dir++)
    for(int dis = 0; dis<=200; dis++)
    {
        if(!dp[i][j][dir][dis]) continue;

        dp[i+1][j+(s[i+1]!='F')][dir][dis+(dir?-1:1)] = 1;
        dp[i+1][j+(s[i+1]!='T')][!dir][dis] = 1;
    }
}

void solve()
{
    int ans = -INF;
    for(int j = m; j>=0; j -= 2)  //一个指令可以修改多次
    for(int dir = 0; dir<2; dir++)
    for(int dis = 0; dis<=200; dis++)
    if(dp[n][j][dir][dis])
        ans = max(ans, abs(100-dis));     //与100的距离，即为实际距离
    cout<<ans<<endl;
}

int main()
{
    init();
    solve();
}

三维DP:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double eps = 1e-6;
const int INF = 2e9;
const LL LNF = 9e18;
const int mod = 1e9+7;
const int maxn = 100+10;

char s[105];
int n,m, dp[110][55][2];

int main()
{
    scanf("%s%d",s+1,&m);
    n = strlen(s+1);
    for(int i = 0; i<=n; i++)
    for(int j = 0; j<=m; j++)
    for(int k = 0; k<2; k++)
        dp[i][j][k] = -INF;

    dp[0][0][0] = dp[0][0][1] = 0;
    for(int i = 0; i<n; i++)
    for(int j = 0; j<=m; j++)
    for(int k = 0; k<2; k++)
    {
        dp[i+1][j+(s[i+1]!='F')][k] = max(dp[i+1][j+(s[i+1]!='F')][k],dp[i][j][k]+(k?1:-1));
        dp[i+1][j+(s[i+1]!='T')][!k] = max(dp[i+1][j+(s[i+1]!='T')][!k],dp[i][j][k]);
    }

    int ans = -INF;
    for (int j = m; j>=0; j -= 2)
        ans = max(ans, max(dp[n][j][0], dp[n][j][1]));

    printf("%d\n",ans);
}