首页 > 代码库 > 简单dp ---HDU3485 Count 101
简单dp ---HDU3485 Count 101
题目大意:让求长度为n的0 和 1 构成的串中不包含101子串的个数有多少。
这个题当时想了好久,以为是一个规律题,一直在推规律,最后还是wa了,上网一看原来是dp问题, 不过确实递推式挺巧妙的。
递推式dp[i] = 2 * dp[i - 1] - dp[i - 2] + dp[i - 3];
现在就来推一下这个式子,首先dp[i]就表示当长度为 i 的 的时候满足条件(就是串中不含101)的个数,dp[i] = 2 * dp[i - 1] - {最后两位是10的个数},其中2 * dp[i-1]就表示总数,最后两位是10的个数就等于 最后一位是0的个数减去倒数第二位是0的个数, 还有一个问题就是最后一位是0怎么求, 最后一个是零的个数就是dp[i-1], 因为当前位的总个数等于前一位乘2, 因为是只有0和1两种状态,所以是0的个数就是前一位的数所以 {最后两位是10的个数} = dp[i - 2] - dp[i - 3]; 所以这个式子最后就是dp[i] = 2 * dp[i - 1] - dp[i - 2] + dp[i - 3];
代码如下:
1 #include<iostream> 2 #include <stdio.h> 3 using namespace std; 4 int dp[10010]; 5 int main() 6 { 7 dp[0] = 0; dp[1] = 2; dp[2] = 4; dp[3] = 7; 8 for (int i = 4; i < 10010; i++) 9 dp[i] = (2 * dp[i - 1] - dp[i - 2] + dp[i - 3]) % 9997 ;10 int n;11 while (~scanf("%d", &n) && n != -1)12 {13 printf("%d\n", dp[n]);14 }15 return 0;16 }
简单dp ---HDU3485 Count 101
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。