snowflake最新欧诶

hzn942 发表于 2020-10-14 13:34
想了半天，第二题思路应该是用两个数组
array_d 和 array_t 分别记录以长度为i+1的时候D和T结尾组合个数， ...

谢谢分享，我也做了同样的题，用了这个解法，全过了，太慢的话应该是implementation的问题

感谢分享。 这个解法可以过所有的test，给你点赞！

1. const int MOD = 1000000007;
   
2. const int M = 200005;
   
3. 
   
4. int add(int x, int y) { return (x % MOD + y % MOD) % MOD; }
   
5. int sub(int x, int y) { return (x % MOD - y % MOD + MOD) % MOD; }
   
6. 
   
7. int dp[M][2];
   
8. 
   
9. vector<int> plantRoses(int w, int r, vector<int> Q) {
   
10.     dp[0][0] = 1;
    
11.     dp[0][1] = 1;
    
12.     dp[1][0] = 1;
    
13.     dp[1][1] = 1;
    
14.     for (int i = 2; i < M; i++) {
    
15.         dp[i][0] = add(dp[i - 1][1], dp[i - 1][0]);
    
16.         if (i >= w) {
    
17.             dp[i][0] = sub(dp[i][0], dp[i - w][1]);
    
18.         }
    
19.         dp[i][1] = add(dp[i - 1][1], dp[i - 1][0]);
    
20.         if (i >= r) {
    
21.             dp[i][1] = sub(dp[i][1], dp[i - r][0]);
    
22.         }
    
23.     }
    
24.     vector<int> ans;
    
25.     for(int i=0; i<Q.size(); i++) {
    
26.         ans.push_back(add(dp[Q[i]][0],dp[Q[i]][1]));
    
27.     }
    
28.     return ans;
    
29. }[/i][/i][/i][/i][/i][/i][/i][/i][i][i][i][i][i][i][i][i]

复制代码

[/i][/i][/i][/i][/i][/i][/i][/i]