Algoogle

Algorithm for Programming Contest

JOI 春合宿 2009 Abduction

Category: JOI Tag: dp

ABduction

問題概要


h*wの格子上を移動した時の左右の方向転換だけわかっている(その格子からはみ出るような移動はない).
このとき, 左下から右上に行く方法は何通りあるか

解法


縦方向の移動と横方向の移動を分けて考える.
左か下に行くときを負の距離の移動とすると
縦方向の移動の総和はh,
横方向の移動の総和はwになる.

よって各方向についてDPしてやればよい.
ある移動で移動する距離で配るDPをする感じ.
dp[i] := 距離iになる場合の数
として, 更新は累積和を取る感じでやればよい(移動0が許されないことに注意する).

コード


(Abduction.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e7;
const int r[4] = {3,2,0,1}, l[4] = {2,3,1,0}, pm[2] = {-1,1};
inline void add(int &a, int b){a=(a+b)%mod;}
inline void mul(int &a, int b){a=1LL*a*b%mod;}

int wh[2], n, dp[1010];
string s;
vector<int> d[2];

int solve()
{
        int dir = ((s[0]=='R')<<1)|1;
        d[dir>>1].push_back(pm[dir&1]);
        for(auto &c: s) {
                if(c=='R') dir = r[dir];
                else dir = l[dir];
                d[dir>>1].push_back(pm[dir&1]);
        }
        int ans = 1;
        for (int k = 0; k < 2; k++) {
                memset(dp,0,sizeof(dp));
                dp[0] = 1;
                for(auto &p: d[k]) {
                        if(p<0) {
                                for (int i = wh[k]-1; i >= 0; i--) add(dp[i],dp[i+1]);
                                for (int i = 0; i < wh[k]; i++) dp[i] = dp[i+1];
                                dp[wh[k]] = 0;
                        }
                        else {
                                for (int i = 1; i <= wh[k]; i++) add(dp[i],dp[i-1]);
                                for (int i = wh[k]; i > 0; i--) dp[i] = dp[i-1];
                                dp[0] = 0;
                        }
                }
                mul(ans, dp[wh[k]]);
        }

        return ans;
}

void input()
{
        cin >> wh[0] >> wh[1] >> n;
        cin >> s;
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments