HDU4632 Palindrome subsequence

标签（空格分隔）：区间qp

Palindrome subsequence

\[求一个string的回文子序列的个数
\]

少废话，上代码。

#include<bits/stdc++.h> //头文件没有什么问题

using namespace std; //名字空间没有什么问题

const int maxn = 1000 +5; // 字符串的最大长度

const int mod = 10007;//题目规定的模数

int n,cnt;//n：有多少个字符串，cnt：记录当前有多少个case

char s[maxn];//字符数组没有什么问题

int dp[maxn][maxn];//dp[i,j]代表[i,j]中有多少个Palindrome subsequence

int main(){

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

		while(n--){

			memset(dp,0,sizeof(dp));

			//置0好习惯！

			scanf("%s",s);

			//输入没有什么问题

			int len = strlen(s);

			//取字符串长度len

			for(int i=0;i<len;i++)

				dp[i][i]=1;

			//每个字符都是一个Palindrome subsequence

			for(int tail=0;tail<len;tail++){

			    //枚举尾

				for(int head=tail-1;head>=0;head--){

					//枚举头，因为头是从后往前推的，所以不会有问题

					dp[head][tail]=(dp[head+1][tail]+dp[head][tail-1]-dp[head+1][tail-1]+mod)%mod;

					//dp[h,t] = dp[h,t-1] + dp[h+1,t] - dp[h+1, t-1],注意取模！<这一步用到了容斥原理>

					if(s[tail]==s[head])

						dp[head][tail]=(dp[head][tail]+dp[head+1][tail-1]+1+mod)%mod;

				    //如果都为相等，则dp[h+1,t-1]中的每个回文子序列都可以增长一个

				    //eg. 1 234 1 , 就可以多出来121，131，141.

				}

			}

			printf("Case %d: %d\n",++cnt,dp[0][len-1]);

		    //输出

		}

	}

	return 0;

    //happy end

}

巴特西

HDU4632 Palindrome subsequence

Palindrome subsequence

最新文章

热门文章