首页 > 代码库 > Gym - 100712D Alternating Strings
Gym - 100712D Alternating Strings
http://codeforces.com/gym/100712/attachments
题意：
给出一个01串，现在要切割这个01串，使得每个子串长度都不大于k，并且每个子串不能01交替出现，单个字符是合法的。
思路：
很容易想到用dp去做，但是怎么做呢？
我们可以先预处理一下i~j是否是合法的子串，即是否是01交替出现的串。
接下来我们从尾部开始，d【i】表示i~n所需的最少切割数。那么每次在左边新加入一个数字时，怎么确定它的最少切割数呢？
设f【i】【t】不是01交替的串并且长度是小于等于k的，那么在t点是可以切割的，我们只需要枚举切割点找最小值就可以了。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath>10 #include<map>11 using namespace std;12 typedef long long ll;13 typedef pair<int,long long> pll;14 const int INF = 0x3f3f;15 const int maxn=1000+5;16 17 int n,k;18 char str[maxn];19 20 int f[maxn][maxn];21 int d[maxn];22 23 int main()24 {25 //freopen("input.txt","r",stdin);26 int T;27 scanf("%d",&T);28 while(T--)29 {30 scanf("%d%d",&n,&k);31 getchar();32 scanf("%s",str+1);33 34 memset(f,0,sizeof(f));35 36 for(int i=1;i<=n;i++)37 {38 f[i][i]=1;39 for(int j=i+1;j<=n;j++)40 {41 if(f[i][j-1] && str[j]!=str[j-1]) f[i][j]=1;42 else break;43 }44 f[i][i]=0;45 }46 47 memset(d,INF,sizeof(d));48 d[n+1]=-1;49 50 for(int i=n;i>=1;i--)51 {52 for(int j=i;j<=i+k-1&&j<=n;j++)53 {54 if(i==j||!f[i][j])55 d[i]=min(d[i],d[j+1]+1);56 }57 }58 59 printf("%d\n",d[1]);60 }61 return 0;62 }
Gym - 100712D Alternating Strings
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。