接下来就是关于数位DP的练习,上来不看别人的解题报告,我选了一道比较简单的题。此题稍微转化一下比上一题不要62还要简单。
这道题需要我们统计数字中含有49的个数,那么我们可以统计不含49的数再减一下就可以了。这样一来就和上一道题几乎一样了。
状态dp[i][j]表示第i为第一位为j所含符合要求的数字数(注意这里是不含49的数)。
程序中预处理出dp数组,然后在用solve计算即可。
代码如下:
1 #include2 #include 3 #include 4 #include 5 #include 6 #define ll long long 7 #define LEN 100 8 using namespace std; 9 10 ll dp[LEN][LEN];11 12 void init()13 {14 memset(dp, 0, sizeof dp);15 for(int i=0; i<10; i++)dp[1][i] = 1;16 for(int i=2; i =1; i--){32 int pos = len+1-i, num = str[pos]-'0';33 for(int j=0; j