usaco 1.1 Broken Necklace（DP）

本文主要是介绍usaco 1.1 Broken Necklace（DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

直接上代码 接触的第一道dp

ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于：

如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0
如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0
如果 str[i] = 'w',  bl[i]=bl[i-1]+1, rl[i]=rl[i-1]+1

dp的思想很明显。

/*
ID: who jay
LANG: C++
TASK: beads
*/#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;int main()
{char str[702],temp[351];int i,n;int bl[705],rl[705],br[705],rr[705];while(scanf("%d",&n)!=EOF){scanf("%s",str);strcpy(temp,str);strcat(str,temp);//left->>rightbl[0]=rl[0]=0;for(i=1; i<=2*n; i++){if(str[i-1]=='b'){bl[i]=bl[i-1]+1;rl[i]=0;}if(str[i-1]=='r'){rl[i]=rl[i-1]+1;bl[i]=0;}if(str[i-1]=='w'){bl[i]=bl[i-1]+1;rl[i]=rl[i-1]+1;}}//right->>leftbr[2*n]=rr[2*n]=0;for(i=2*n-1; i>=0; i--){if(str[i]=='b'){br[i]=br[i+1]+1;rr[i]=0;}if(str[i]=='r'){rr[i]=rr[i+1]+1;br[i]=0;}if(str[i]=='w'){br[i]=br[i+1]+1;rr[i]=rr[i+1]+1;}}int m=0;//左右都从i位置开始遍历for(i=0; i<2*n; i++){m=max( m , max(bl[i],rl[i]) + max(br[i],rr[i]) );}m=min(m,n);printf("%d\n",m);}return 0;
}

ko题目的感觉很爽 但是才刚刚起步 继续努力！

这篇关于usaco 1.1 Broken Necklace（DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---