首页 > 代码库 > hdu--4632--dp
hdu--4632--dp
dp我突然觉得 没必要将它仔细地分成各种种类 都是利用了差不多什么递推 利用前面计算出来的子结果什么的思想
这题的状态 不难想 因为一个回文串肯定是有左右端点啊 那么就肯定有2维状态了 然后就是递推吧
这边有些初始化 可以先完成 也可以在解决的时候 一并完成 随你
我一开始自己写的是 记忆化搜索的写法. 然后有人写了直接for递推的 速度比我这 递归的快了3倍吧
我把2种都贴上来 顺便写下 状态转移方程
dp[x][y] = dp[x][y-1] + dp[x+1][y] - dp[x+1][y-1] if str[x]==str[y] dp[x][y] += dp[x+1][y-1] + 1;
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 const int size = 1010; 6 const int mod = 10007; 7 int len; 8 char str[size]; 9 int dp[size][size];10 11 int dfs( int L , int R )12 {13 if( L<1 || R>len || L>R )14 return 0;15 if( dp[L][R] )16 return dp[L][R];17 if( L==R )18 {19 dp[L][R] = 1;20 }21 else if( L+1==R ) 22 {23 if( str[L]==str[R] )24 {25 dp[L][R] = 3;26 }27 else28 {29 dp[L][R] = 2;30 }31 }32 else33 {34 if( str[L] == str[R] )35 dp[L][R] = ( dfs( L , R-1 ) + dfs( L+1 , R ) + 1 ) % mod ;36 else37 dp[L][R] = ( dfs( L , R-1 ) + dfs( L+1 , R ) - dfs( L+1 , R-1 ) + mod ) %mod;38 }39 return dp[L][R];40 }41 42 int main()43 {44 int t , ans;45 scanf("%d",&t);46 for( int k = 1 ; k<=t ; k++ )47 {48 cin >> (str+1);49 len = strlen(str+1);50 memset( dp , 0 , sizeof(dp) );51 ans = dfs( 1 , len );52 printf("Case %d: %d\n",k,ans%mod);53 }54 return 0;55 }
那个for循环的外层是区间长度 内存是左边端点起始坐标 这个递推顺序一定不能错 你可以根据你的状态转移方程来确定
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 const int size = 1010; 6 const int mod = 10007; 7 int len; 8 char str[size]; 9 int dp[size][size];10 11 void solve( )12 {13 for( int i = 1 ; i<=len ; i++ )14 {15 for( int j = 1 ; j+i<=len ; j++ ) 16 {17 if( str[j] == str[i+j] )18 dp[j][i+j] = dp[j+1][i+j] + dp[j][i+j-1] + 1;19 else20 dp[j][i+j] = dp[j+1][i+j] + dp[j][i+j-1] - dp[j+1][i+j-1];21 dp[j][i+j] = (dp[j][i+j]+mod)%mod;22 }23 }24 }25 26 int main()27 {28 int t , ans;29 scanf("%d",&t);30 for( int k = 1 ; k<=t ; k++ )31 {32 cin >> (str+1);33 len = strlen(str+1);34 memset( dp , 0 , sizeof(dp) );35 for( int i = 1 ; i<=len ; i++ )36 dp[i][i] = 1;37 solve( );38 printf("Case %d: %d\n",k,dp[1][len]%mod);39 }40 return 0;41 }
today:
11.11 童话里都是骗人的
hdu--4632--dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。