E - Exploring Pyramids Gym - 101334E 分治

本文主要是介绍E - Exploring Pyramids Gym - 101334E 分治，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

给出一段序列，从一个点开始回到这个点，问这个序列是否符合这个轨迹

题解：

分治，看代码就可以懂了

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;#define LL long long
#define mod 1000000000
LL dp[320][320];
char str[310];LL deal(int left,int right)
{if(dp[left][right]!=-1)    return dp[left][right];if(right==left)            return 1;if(str[left]!=str[right])  return 0;dp[left][right]=0;for(int i=left+2;i<=right;i++){if(str[i]==str[right]&&str[i]==str[left])dp[left][right]=(dp[left][right]+deal(left+1,i-1)*deal(i,right))%mod;}return dp[left][right];
}int main()
{//freopen("in.txt","r",stdin);freopen("exploring.in","r",stdin);freopen("exploring.out","w",stdout);while(scanf("%s",str)!=EOF){int len=strlen(str)-1;memset(dp,-1,sizeof(dp));printf("%lld\n",deal(0,len));}return 0;
}

这篇关于E - Exploring Pyramids Gym - 101334E 分治的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---