【牛客-21302】被3整除的子序列（动态规划）

被3整除的子序列

题目描述

给你一个长度为50的数字串,问你有多少个子序列构成的数字可以被3整除
答案对1e9+7取模

输入描述:

输入一个字符串，由数字构成，长度小于等于50

输出描述:

输出一个整数

示例1

输入

132

输出

3

示例2

输入

9

输出

1

题目链接：

https://ac.nowcoder.com/acm/problem/21302（现在牛客注册）

这题仔细想想，可以这样写，每个数字串都可以从第一个最后一个去考虑，设初始子序列个数为len，每增加一个数，子序列就变为2*len+1；

设dp[0],dp[1],dp[2],表示除3得到的余数分别为0,1,2。每增加一个数就更新一遍数组。

余数为0：dp[0]=dp[0]+dp[0]+1;

　　　　 dp[1]=dp[1]+dp[1];

　　　　 dp[2]=dp[2]+dp[2];

余数为1：dp[0]=dp[0]+dp[2];

　　　　 dp[1]=dp[1]+dp[0]+1;

　　　　 dp[2]=dp[2]+dp[1];

余数为2：dp[0]=dp[0]+dp[1]；

　　　　 dp[1]=dp[1]+dp[2];

　　　　 dp[2]=dp[2]+dp[0]+1;

这个规律自己找几个数测一下就有了

AC代码

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <fstream>
 4 #include <algorithm>
 5 #include <cmath>
 6 #include <deque>
 7 #include <vector>
 8 #include <queue>
 9 #include <string>
10 #include <cstring>
11 #include <map>
12 #include <stack>
13 #include <set>
14 using namespace std;
15 const int Mod=1e9+7;
16 char ch[1000];
17 int dp[3];
18 int f(char s)//字符串转换整数
19 {
20     return s-'0';
21 }
22 int main()
23 {
24     cin.getline(ch,1000);
25     memset(dp,0,sizeof(dp));
26 
27     int len=strlen(ch);
28     for(int i=0; i<len; i++)//开始从第一个数遍历
29     {
30         /*
31         重点来了，这步不能省，必须要开新的数保存，暂时不能改变dp的大小
32         等s0,s1,s2全部更新完以后才能去换，不然会影响结果，
33         假设余数为2：dp[0]=dp[0]+dp[1]；
34 　　　　             dp[1]=dp[1]+dp[2];
35 　　　　             dp[2]=dp[2]+dp[0]+1;
36         如果这样这样更新会有一个问题，dp[0]改变之后，dp[2]=dp[2]+dp[0]+1;
37         用的就是新的dp[0],答案就不符合了
38         */
39         int s0=0,s1=0,s2=0;
40         int x=f(ch[i]);
41         if(x%3==0)
42         {
43            s0+=dp[0]+1;
44            s1+=dp[1];
45            s2+=dp[2];
46         }
47         if(x%3==1)
48         {
49             s0+=dp[2];
50             s1+=dp[0]+1;
51             s2+=dp[1];
52         }
53         if(x%3==2)
54         {
55             s0+=dp[1];
56             s1+=dp[2];
57             s2+=dp[0]+1;
58         }
59         //统一更新
60         dp[0]+=s0;
61         dp[1]+=s1;
62         dp[2]+=s2;
63         for(int j=0; j<3; j++)//每次对1e9+7取余；
64             dp[j]=dp[j]%Mod;
65     }
66     cout << dp[0] << endl;
67 }