首页 > 代码库 > poj 2346 Lucky tickets
poj 2346 Lucky tickets
题目链接：http://poj.org/problem?id=2346
思路：
使用动态规划解法：
设函数 d( n, x )代表长度为n且满足左边n/2位的和减去右边n/2位的和为x的数的数目。
将一个长度为n的数看做n个数字 A1, A2....An ( 0 <= Ai <= 9 )，将字符分为两个集合{ A1, A2....An/2 } 与 { An/2+1.....An };
问题转换为求集合中元素和相等的数目。先从每个集合中选出一个元素，求它们差为a的可能数目，即d( 2, a );
再求两个集合剩下的元素和的差为 x - a 的数目，即d( n -2, x -a )；所以动态递归方程为 d( n, x ) = ∑ d( n - 2, x - a ) * d( 2, a ); (-9<=a<=9)
可以使用记忆搜索求解。
代码：
#include <stdio.h>#include <math.h>#include <string.h>const int MAX_N = 11;int dp[MAX_N][MAX_N];int d( int n, int x ){ if ( dp[n][x] != -1 ) return dp[n][x]; if ( n == 2 ) { int sum = 0; for ( int a = 0; a <= 9; ++a ) for ( int b = 0; b <= 9; ++b ) if (a - b == x) sum++; return dp[n][x] = sum; } else { int a, b, sum = 0; for ( b = -9; b <= 9; ++b ) { a = x - b; if (a >= -9 * (n - 2) / 2 && a <= 9 * (n - 2) / 2) sum += d(n - 2, abs(a)) * d(2, abs(b) ); } return dp[n][x] = sum; } }int main(){ int n; long long ans = 0; memset(dp, -1, sizeof(dp)); scanf("%d", &n); ans = d(n, 0); printf("%lld\n", ans); return 0;}
poj 2346 Lucky tickets
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。