Codeforces Beta Round #96 (Div. 2) E. Logo Turtle dp

http://codeforces.com/contest/133/problem/E

题目就是给定一段序列，要求那个乌龟要走完整段序列，其中T就是掉头，F就是向前一步，然后开始在原点，起始方向随意，要求输出能走到最远是哪里。

首先可以保证的是，他最远走的可以默认是向右走，因为，如果你说是向左走的话，我可以设置相反的开始face，就是开始的时候面向那里，从而得到相反的结论。所以就能得到向左走，是-1，向右走，是+1

那么从最终状态考虑，

最后肯定是走完了整段序列，然后改变了n次，face是那里还不清楚的，所以就是dp[i][j][face]能表达完状态。

face : 0 or 1

dp[i][j][face]表示走完前i个，改变了j次，最后face向哪里的时候的最优解

那么转移过来的时候：

因为一个点可以改变很多次，所以。

for (int i = 1; i <= lenstr; ++i) //枚举整段序列（这是必须的）

　　for (int j = 0; j <= n; ++j) //枚举前i个位置一共改变了多少次

　　　　for (int h = 0; h <= j; ++h) //枚举第i个位置改变了多少次（因为可以重复改变）

如果同一个点改变了奇数次，相当于没变。以此类推

所以就能从dp[i - 1][j - h][face]这个转移到下一个

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

const int maxn =  + ;

int dp[maxn][maxn][];

char str[maxn];

void work() {

    int n;

    for (int i = ; i <= maxn - ; ++i) {

        for (int j = ; j <= maxn - ; ++j) {

            for (int k = ; k < ; ++k) {

                dp[i][j][k] = -inf;

            }

        }

    }

    dp[][][] = ;

    dp[][][] = ;

    scanf("%s%d", str + , &n);

    for (int i = ; str[i]; ++i) {

        for (int j = ; j <= n; ++j) {

            for (int h = ; h <= j; ++h) {

                if (str[i] == 'T') {

                    if (h & ) {

                        dp[i][j][] = max(dp[i][j][], dp[i - ][j - h][] + );

                        dp[i][j][] = max(dp[i][j][], dp[i - ][j - h][] - );

                    } else {

                        dp[i][j][] = max(dp[i][j][], dp[i - ][j - h][]);

                        dp[i][j][] = max(dp[i][j][], dp[i - ][j - h][]);

                    }

                } else { // 'F'

                    if (h & ) { //to 'T'

                        dp[i][j][] = max(dp[i][j][], dp[i - ][j - h][]);

                        dp[i][j][] = max(dp[i][j][], dp[i - ][j - h][]);

                    } else {

                        dp[i][j][] = max(dp[i][j][], dp[i - ][j - h][] + );

                        dp[i][j][] = max(dp[i][j][], dp[i - ][j - h][] - );

                    }

                }

            }

        }

    }

    int lenstr = strlen(str + );

    int ans = max(dp[lenstr][n][], dp[lenstr][n][]);

    cout << ans << endl;

}

int main() {

#ifdef local

    freopen("data.txt","r",stdin);

#endif

    work();

    return ;

}

巴特西

Codeforces Beta Round #96 (Div. 2) E. Logo Turtle dp

最新文章

热门文章