广州公司注销可以网上办理_外包服务是什么意思_seo顾问服务深圳_中国网络营销公司

题目如下

数据范围

示例

本题难就难在要找到转移的方法。
令f(i,j) 其中1 <= j <= 4 为以j个相同数字为结尾的可能数。
f(0,1)显然等于1
f(i,1) = f(i - 1,1) + f(i - 1,2) + f(i - 1,3) + f(i - 1,4)
f(i,2) = f(i,1)
f(i,3) = f(i - 1,2)
f(i,4)(注意对应的数值7或9) = f(i - 1,3)

通过代码(未优化)

class Solution {
public:int count(int d,int ans,int n){int mod = 1e9 + 7;vector<vector<long long>> dp(n,vector<long long>(5,0));dp[0][1] = 1;for(int i = 1;i < n;i++){dp[i][1] = (dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3] + dp[i - 1][4]) % mod;dp[i][2] = dp[i - 1][1];dp[i][3] = dp[i - 1][2];if(d == 7 || d == 9){dp[i][4] = dp[i - 1][3];}}int t = (dp[n - 1][1] + dp[n - 1][2] + dp[n - 1][3] + dp[n - 1][4]) % mod;return (1l * ans * t) % mod;}int countTexts(string pressedKeys) {int n = pressedKeys.size();int ans = 1;int r,l = 0;while(true){r = l;while(r <= n - 1&& pressedKeys[r] == pressedKeys[l])r++;//   cout << pressedKeys[l] - '0' << " " << r - l << " \n";ans = count(pressedKeys[l] - '0',ans,r - l);l = r;if(l >= n - 1)break;}return ans;}
};

通过代码(已优化)

class Solution {
public:int count(int di,int ans,int n){int mod = 1e9 + 7;long long a ,b,c,d;long long t1,t2,t3;a = 1;b = c = d = 0;for(int i = 1;i < n;i++){t1 = a;t2 = b;t3 = c;a = (a + b + c + d) % mod;b = t1;c = t2;if(di == 7 || di == 9)d = t3;}int t = (a + b + c + d) % mod;return (1l * ans * t) % mod;}int countTexts(string pressedKeys) {int n = pressedKeys.size();int ans = 1;int r,l = 0;while(true){r = l;while(r <= n - 1&& pressedKeys[r] == pressedKeys[l])r++;//   cout << pressedKeys[l] - '0' << " " << r - l << " \n";ans = count(pressedKeys[l] - '0',ans,r - l);l = r;if(l >= n - 1)break;}return ans;}
};