hdu-4632 Palindrome subsequence

本文主要是介绍hdu-4632 Palindrome subsequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Palindrome subsequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65535 K (Java/Others)
link
比较裸的区间dp

#include<stdio.h>
#include<string.h>
using namespace std;
const int mod=10007;int dp[1005][1005];
int main(){int t;int cas=1;char a[1005];scanf("%d",&t);while(t--){int i,j,k;scanf("%s",a+1);int len=strlen(a+1);for(i=1;i<=len;i++)dp[i][i]=1;int x;for(k=2;k<=len;k++)for(i=1,j=k;j<=len;i++,j++){dp[i][j]=(dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]+mod)%mod;if(a[i]==a[j]){dp[i][j]=(dp[i][j]+dp[i+1][j-1]+1+mod)%mod;}}printf("Case %d: %d\n",cas++,dp[1][len]);}return 0;
}

这篇关于hdu-4632 Palindrome subsequence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---