首页 > 代码库 > codeforces313B - Ilya and Queries DP

codeforces313B - Ilya and Queries DP

题意:问你字符串一定范围能 s[i] = s[i-1]的个数

解题思路:简单dp

解题代码:

 1 // File Name: 313b.cpp 2 // Author: darkdream 3 // Created Time: 2014年07月24日 星期四 08时02分38秒 4  5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 25 using namespace std;26 char str[100005];27 int  sum[100005];28 int main(){29    scanf("%s",&str[1]);30    int len = strlen(&str[1]);31    sum[1] = 0 ; 32    for(int i =1;i <= len ;i ++)33    {34      if(str[i+1] == str[i])35       {36         sum[i] = sum[i-1] + 1;  ; 37       }else{38         sum[i] = sum[i-1];39       }40    }41    int m ; 42    scanf("%d",&m);43    for(int i =1 ;i <= m ;i ++)44    {45       int l, r; 46       scanf("%d %d",&l,&r);47       printf("%d\n",sum[r-1]- sum[l-1]);48    }49 return 0;50 }
View Code