牛客練習賽13E 龜兔賽跑DP

E:

烏龜跑步

有一隻烏龜，初始在0的位置向右跑。

這隻烏龜會依次接到一串指令，指令T表示向後轉，指令F表示向前移動一個機關。烏龜不能忽視任何指令。

現在我們要修改其中正好n個指令（一個指令可以被改多次，一次修改定義為把某一個T變成F或把某一個F變成T）。

求這隻烏龜在結束的時候離起點的最遠距離。（假設烏龜最後的位置為x，我們想要abs(x)最大，輸出最大的abs(x)

輸入描述:

第一行一個字元串c表示指令串。c隻由F和T構成。
第二行一個整數n。
1 <= |c| <= 100, 1 <= n <= 50      

輸出描述:

一個數字表示答案。      

輸入

FT
1      

輸出

2      

題目分析:這個就是DP了，dp[i][j][k][status] 表示執行i個指令，更改j次，是否能到達k這個位置并且朝status(0/1)方向。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;

#define x0 x0___
#define y0 y0___
#define pb push_back
#define SZ(X) ((int)X.size())
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define ALL(X) X.begin(),X.end()
#define RALL(X) X.rbegin(),X.rend()
#define rep(i,j,k) for(int i = j;i <= k;i ++)
#define per(i,j,k) for(int i = j;i >= k;i --)
#define mem(a,p) memset(a,p,sizeof(a))


const ll MOD = 1E9 + 7;
ll qmod(ll a,ll b,ll c) {ll res=1;a%=c; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%c;a=a*a%c;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

template<typename T, typename S>
void upmax(T& a,S b){if(a<b) a=b;}
template<typename T, typename S>
void upmin(T& a,S b){if(a>b) a=b;}
template<typename T>
void W(T b){cout << b << endl;}
void gettle() {while(1);}
void getre() {int t=0;t/=t;}


/
/
/
/

const int N = 107;
bool dp[N][N>>1][N<<1][2];
char s[N];

int main()
{
    dp[0][0][101][1] = 1; //初值在101,朝右status為1

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

    rep (i,1,n) {
        rep (j,0,m) {
            rep (k, 1, 201) {
                if(s[i] == 'F') {
                    if(j) dp[i][j][k][1] |= dp[i - 1][j - 1][k][0]; //翻轉變轉向 F->T
                    if(j) dp[i][j][k][0] |= dp[i - 1][j - 1][k][1];
                    dp[i][j][k + 1][1] |= dp[i - 1][j][k][1]; //往右
                    dp[i][j][k - 1][0] |= dp[i - 1][j][k][0]; //往左
                    if(j >= 2) dp[i][j][k + 1][1] |= dp[i-1][j - 2][k][1]; //翻轉2次
                    if(j >= 2) dp[i][j][k - 1][0] |= dp[i-1][j - 2][k][0];
                } else { //同上
                    if(j) dp[i][j][k + 1][1] |= dp[i - 1][j - 1][k][1];
                    if(j) dp[i][j][k - 1][0] |= dp[i - 1][j - 1][k][0];
                    dp[i][j][k][1] |= dp[i - 1][j][k][0];
                    dp[i][j][k][0] |= dp[i - 1][j][k][1];
                    if(j >= 2) dp[i][j][k][1] |= dp[i - 1][j - 2][k][0];
                    if(j >= 2) dp[i][j][k][0] |= dp[i - 1][j - 2][k][1];
                }
            }
        }
    }

    int res = 0;
    rep (i,1,201) {
        if(dp[n][m][i][0] || dp[n][m][i][1]) upmax(res, abs(i - 101) );
    }

    return !printf("%d\n", res);
}