Strings+dp - Codeforces

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Jamie is walking along a number line that starts at point 0 and ends at point n. She can move either one step to the left or one step to the right of her current location , with the exception that she cannot move left from point 0 or right from point n. In other words, if Jamie is standing at point i,she can move to either i-1 or i+1 as long as her destination exists in the inclusive range [0,n]. She has a string ,s , of movement instruction consisting of the letters 1 and r , where 1 is an instruction to move one step left and r is an instruction to move one step right. Jamie followed the instructions in s one by one and in order .For Example if s=‘rrlr’,she performs the following sequence of moves :one step right ->one step right ->one step left -> one step right .Jamie wants to move from point x to point y following some subsequence of string s instruction and wonders how many distinct possible subsequence of string s will get her from point x to point y. recall that a subsequence of a string is obtained by deleting zero or more characters from string .

it has four parameters A String , s giving a sequence of eduction using the characters l( i.e. move left one unit ) and r (i.e. move right one unit) An integer n, denoting the length of the number line. An integer x, denoting jamie’s starting point on the number line An integer y , denoting Jamie’s enidng point on the number line. The function must return an integer denoting the total number of distinct subsequence of string s that will lead Jamie from point x to point y as this value cab be quite large .

Sample Input rrlrlr 6 1 2

out put =7

r
rrl
rlr
lrr
rrlrl
rlrlr
rrllr

Комментарии (5)

Показать архивные | Написать комментарий?

R.A.N.K.A.

4 года назад, # |

Auto comment: topic has been updated by R.A.N.K.A. (previous revision, new revision, compare).

→ Ответить

hg333

If the constraints allow, you can do a knapsack-style dp considering r to be +1, and l to be -1, and also adding the boundary conditions.

yranka309

← Rev. 4 →

This Problem Can be solved using dp

here is my solution :-

Code


#include <bits/stdc++.h>
using namespace std;

#define mod 1000000007

int dp[1001][2501][2];

int solveUtil( string moves, int n, int start, int end, int idx, bool flag ){

	if(start < 0 || start >n )
		return 0;
	
	if(start == end && idx == moves.size() )
		return 1;
	
	if(idx>= moves.size())
		return 0;

	int &ans=dp[idx][start][flag];
	if(ans!=-1)	return ans;
	ans=0;
	
	if( (moves[idx] == 'l' && flag) || (moves[idx] == 'r' && !flag) )
	{
	
		int change = moves[idx] == 'l' ? -1 : 1;
		int x=solveUtil( moves, n, start+change, end, idx+1, flag );
		int y=solveUtil( moves, n, start+change, end, idx+1, !flag );
		ans=(x+y)%mod;
	}
	else
		ans = solveUtil( moves, n, start, end, idx+1, flag );
	
	return ans;
}
	
int solve( string moves, int n, int start, int end ){
	
	memset(dp,-1,sizeof(dp));
	return solveUtil( moves, n, start, end, 0, false ) + solveUtil( moves, n, start, end, 0, true );
}

int main() {
	string step;
	cin >> step;
	int n,s,e;
	cin >> n >> s >> e;
	cout << solve( step, n, s, e ) << endl;
	return 0;
}

gladgeek

3 года назад, # ^ |

not working for string rrlrlr with n =6 and s=1 and e=4

your solution is giving answer 4 but correct result is 3

FOo_bar_2

← Rev. 2 →

A simple DP would work.

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;

int main()
{

    string s;
    int N, from, to;
    cin >> s >> N >> from >> to;
    int n = s.length();
    
    vector<int> nxtl(n, -1), nxtr(n, -1);
    int lastl = -1, lastr = -1;
    for (int i = n - 1; i >= 0; i--)
    {
        if (s[i] == 'l')
            lastl = i;
        else
            lastr = i;
        nxtl[i] = lastl;
        nxtr[i] = lastr;
    }

    vector<vector<int>> dp(n + 1, vector<int>(N + 1));
    dp[0][from] = 1;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= N; j++)
        {
            if (j + 1 <= N and nxtr[i] != -1)
            {
                dp[nxtr[i] + 1][j + 1] += dp[i][j];
                dp[nxtr[i] + 1][j + 1] %= mod;
            }
            if (j - 1 >= 0 and nxtl[i] != -1)
            {
                dp[nxtl[i] + 1][j - 1] += dp[i][j];
                dp[nxtl[i] + 1][j - 1] %= mod;
            }
        }
    }

    int ans = 0;

    for (int i = 0; i <= n; i++)
    {
        ans += dp[i][to];
        ans %= mod;
    }

    cout << ans << endl;

    return 0;
}

Блог пользователя R.A.N.K.A.