【Hello】

【问题描述】

Alice和Bob有一个长度为2n的数。现在他们要在这个数字上玩游戏。他们分别要从2n个位中取出n个位组成自己的幸运值。每一回合,Alice或Bob把数学最左边的那一位拿出来放在自己幸运值的最末位。在第i轮操作过后,被选取的数位(原数的第i位)会从原数中消失。现在Alice和Bob想要使得他们两个幸运值的和尽可能大。请求出这个值。

【输入格式】

一个整数位幸运值的和的最大值。

【输入样例】

2

1234

【输出样例】

46

【样例说明】

Alice取1、2位。Bob取3、4位。幸运值分别为12和34,和为46。

【数据范围】

对30%的输入数据:n<=10;

对100%的输入数据:n<=18,原数与幸运值均允许前缀0的存在。

DP题,用dp[i][j]表示Alice选了前i位,Bob选了前j位的最优解,那么当前要选的就是第i+j+1位数,如果给Alice,那么它对答案的贡献是10n-i-1同样的,对于Bob则是10n-j-1。则DP方程式易推出,注意当取到n时对答案的贡献是1,不能用pow函数不然会计算10的-1次方的。

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*