【尺取或dp】codeforces C. An impassioned circulation of affection

http://codeforces.com/contest/814/problem/C

【题意】

给定一个长度为n的字符串s，一共有q个查询，每个查询给出一个数字m和一个字符ch，你的操作是可以改变字符串中的某些字母，最多改变m个，问操作后只包含字符ch的连续子序列最长是多少？

【思路】

方法一：

有这么一类问题，需要在给的一组数据中找到不大于某一个上限的“最优连续子序列”

于是就有了这样一种方法，找这个子序列的过程很像毛毛虫爬行方式比较流行的叫法是“尺取法”。

有关尺取的练习：

http://blog.csdn.net/acmer_sly/article/details/59524223

http://acm.hdu.edu.cn/showproblem.php?pid=5328

尺取是线性的，所以总的时间复杂度是O(qn).

方法二：
dp,对每个字母预处理，时间复杂度是O(26n^2)。

【Accepted】

 #include <iostream>

 #include <stdio.h>

 #include <cmath>

 #include <vector>

 #include <algorithm>

 #include <set>

 #include <map>

 #include <queue>

 #include <deque>

 #include <stack>

 #include <string>

 #include <bitset>

 #include <ctime>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 typedef long long ll;

 const int maxn=;

 int n,q,m;

 char s[maxn];

 char ch[];

 int solve(char c)

 {

     //双指针

     int l=,r=;

     int ans=;

     int cnt=;

     while(l<n&&r<n)

     {

         //右端点不断往后扫，直到不能再向右

         while(r<n && (s[r]==c||cnt<m))

         {

             if(s[r]!=c)

             {

                 cnt++;

             }

             r++;

         }

         //记下当前l下的解

         ans=max(ans,r-l);

         while(l<=r && s[l]==c)

         {

             l++;

         }

         //找到第一个使cnt-1的l,r才能继续向右更新

         l++;

         cnt--;

     }

     return ans;

 }

 int main()

 {

     while(~scanf("%d",&n))

     {

         scanf("%s",s);

         scanf("%d",&q);

         for(int i=;i<q;i++)

         {

             scanf("%d%s",&m,ch);

             int ans=solve(ch[]);

             printf("%d\n",ans);

         }

     }

     return ;

  } 

尺取

 #include <iostream>

 #include <stdio.h>

 #include <cmath>

 #include <vector>

 #include <algorithm>

 #include <set>

 #include <map>

 #include <queue>

 #include <deque>

 #include <stack>

 #include <string>

 #include <bitset>

 #include <ctime>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 typedef long long ll;

 int n,q,m;

 const int maxn=;

 char s[maxn];

 int dp[maxn][];

 char ch[];

 void Init()

 {

     memset(dp,-,sizeof(dp));

     for(int c=;c<;c++)

     {

         for(int i=;i<n;i++)

         {

             int num=;

             for(int k=i;k>=;k--)

             {

                 if(s[k]==(char)(c+'a'))

                 {

                     num++;

                 }

                 //替换i-k+1-num个字母达到的子段长度是i-k+1,枚举所有的子段不断更新，找到最大值，共n^2个子段。

                 dp[i-k+-num][c]=max(dp[i-k+-num][c],i-k+);

             }

         }

     }

 }

 int main()

 {

     while(~scanf("%d",&n))

     {

         scanf("%s",s);

         Init();

         scanf("%d",&q);

         for(int i=;i<q;i++)

         {

             scanf("%d%s",&m,&ch);

             if(dp[m][ch[]-'a']==-)

             {

                 printf("%d\n",n);

             }

             else

             {

                 printf("%d\n",dp[m][ch[]-'a']);

             }

         }

     }

     return ;

 }

dp