【训练题71：动态规划】Building Blocks | Gym102822B

代码

• 时间复杂度：$O(n+m)$

#include 
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long ll;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x <<  " ] , ";show(args...);}

const int MAX = 2e5+50;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-5;

ll qpow(ll a,ll n){/* */ll res = 1LL;while(n){if(n&1)res=res*a%MOD;a=a*a%MOD;n>>=1;}return res;}
ll qpow(ll a,ll n,ll p){a%=p;ll res = 1LL;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
ll npow(ll a,ll n){/* */ll res = 1LL;while(n){if(n&1)res=res*a;a=a*a;n>>=1;if(res<0||a<0)return 0;}return res;}
ll inv(ll a){/* */return qpow(a,MOD-2);}
ll inv(ll a,ll p){return qpow(a,p-2,p);}

unordered_map<int,bool>M[MAX];
int aa[MAX];
int cnt[MAX];
ll dp[MAX][2];

int F(int n,int m){
    return n + m - 1;
}

int main()
{
    int T;
    scanf("%d",&T);
    for(int kase = 1;kase <= T;++kase){
        ll ans = 0;
        int n,m,k;
        scanf("%d%d%d",&n,&m,&k);
        int min_nm = min(n,m);

        for(int i = 1;i <= n + m;++i){
            M[i].clear();
        }
        for(int i = 1;i <= min_nm;++i){
            cnt[i] = i;
        }
        for(int i = min_nm;i <= n + m - 1;++i){
            cnt[i] = min_nm;
        }
        for(int i = 1;i <= min_nm;++i){
            cnt[n + m - i] = i;
        }


        for(int i = 1;i <= n + m;++i){
            scanf("%d",&aa[i]);
        }

        bool cant = false;

        for(int i = 1;i <= k;++i){
            int x,y,h;
            scanf("%d%d%d",&x,&y,&h);
            int aim = F(x,y);
            M[aim][h] = 1;
            cnt[aim]--;
            if(h > aa[aim] || h > aa[aim+1]){
                cant = true;
                
            }
        }

        if(aa[1] > aa[2]){
            cant = true;
        }
        if(cnt[1] == 0 && !M[1][aa[1]]){
            cant = true;
        }

        if(!cant){
            // init
            dp[1][1] = dp[1][0] = 0;

            if(aa[1] == aa[2]) dp[1][1] = 1;
            else dp[1][0] = 1;

            for(int i = 2;i <= n + m - 1;++i){
                dp[i][0] = dp[i][1] = 0;
                int a = aa[i],b = aa[i+1];
                int k = min(a,b);
                bool ys = M[i][k];
                int ccnt = cnt[i];
                ll rem = (qpow(k,ccnt) - qpow(k-1,ccnt) + MOD) % MOD;

                // dp[i-1][1]
                if(b <= a){
                    if(ys) dp[i][1] = (dp[i][1] + dp[i-1][1] * qpow(b,ccnt) % MOD) % MOD;
                    else dp[i][1] = (dp[i][1] + dp[i-1][1] * rem % MOD) % MOD;
                }


                if(b <= a && !ys){
                    dp[i][0] = (dp[i][0] + dp[i-1][1] * qpow(b-1,ccnt) % MOD) % MOD;
                }else if(a < b){
                    dp[i][0] = (dp[i][0] + dp[i-1][1] * qpow(a,ccnt) % MOD) % MOD;
                }

                // dp[i-1][0]
                if(a > b){
                    //no solution
                }else if(a < b){
                    if(ys)  dp[i][0] = (dp[i][0] + dp[i-1][0] * qpow(a,ccnt) % MOD) % MOD;
                    else dp[i][0] = (dp[i][0] + dp[i-1][0] * rem % MOD) % MOD;
                }else if(a == b){
                    if(ys)  dp[i][1] = (dp[i][1] + dp[i-1][0] * qpow(a,ccnt) % MOD) % MOD;
                    else dp[i][1] = (dp[i][1] + dp[i-1][0] * rem % MOD) % MOD;
                }
//                show(i,dp[i][0],dp[i][1]);
            }

            ans = dp[n+m-1][1];
        }

        printf("Case #%d: %lld\n",kase,ans);
    }
    return 0;
}
/**

*/

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128