2016弱校连萌Round 1l Liesbeth and the String

题目链接

Liesbeth and the String

方法： 动态规划推公式

题目分析

题目大意

给定一个含有n个a的字符串，然后对这个字符串进行如下操作

• 以a开头，则移除前两个字母，字符串末尾补上bc
• 以b开头，则移除前两个字母，字符串末尾补上a
• 以c开头，则移除前两个字母，字符串末尾补上aaa

问，对这个字符串进行多少次操作可以使这个字符串只留下一个字符？

解析

偶数的情况是比较好推断的，n组aa可以形成n组bc，n组bc可以形成n个a，所以dp[n]=dp[n/2]+n, n为偶数，但是奇数的情况需要推一下，以11为例，可以推算出，dp[n]=dp[n/2*3+2]+n+1，找到规律之后会发现，这是一个环，偶数从比他小的数推出来，奇数会从n/2*3+i+1的数算出来，所以奇数会一直往上递归，找到一个偶数之后，再一直往下算，最终算到dp[1]。当然，有个比较坑的地方是，函数的形参为long long类型。

代码

#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#define eps 1e-8
#define INF 0x3f3f3f3f
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
#define maxn 100000+5
#define mod 1000000007
ll dp[]={0,0,2,24,6,20,30,128,14,152,30,120,42,64,142,300,30,108,170,236,50,84,142,284,66,300,90,40656,170,216,330,40524,62,384,142,260,206,264,274,996,90,40628,126,596,186,256,330,40492,114,388,350,520,142,224,40710,41040,226,740,274,956,390,484,40586,42160,126,552,450,672,210,316,330,40444,278,41224,338,700,350,468,1074,1860,170,688,40710,40984,210,340,682,1200,274,896,346,39556,422,564,40586,42096,210,41468,486,812,450,604,622,39120,246,2124,330,40372,40818,40984,41150,34620,338,624,854,1232,390,568,1074,1780,510,39860,606,2720,40710,40900,42286,11404,254,41792,682,1112,582,784,806,2532,346,39464,454,2132,470,684,40586,42000,422,41348,41370,41852,486,712,850,1744,502,1616,622,39016,1230,1468,2018,23612,330,40264,850,1384,40874,41124,41150,34508,378,11828,510,42648,854,1116,1374,38276,450,1228,1074,1660,526,800,39738,40820,606,2596,750,3916,40774,41060,42286,11276,402,41832,41662,42300,682,980,1010,45388,650,2248,806,2396,826,1136,39326,41368,454,1992,2334,3024,542,864,40586,41856,41034,1928,41202,5468,41370,41704,34842,38364,562,12392,850,1592,1082,1428,1462,48176,622,38860,802,47172,1310,1668,2018,23452,750,1404,40102,40896,850,1220,2966,4424,40958,4540,41150,34340,42538,42920,11658,26456,510,42476,42050,42896,942,1336,1374,38100,846,46052,1050,2876,1074,1480,2802,5472,618,1820,39738,40636,730,1148,2410,4056,750,3728,966,33144,40870,41300,42286,11084,710,2652,41638,42588,41662,42104,42146,9068,782,39108,1010,45188,1150,1604,2046,10124,806,2192,1922,2924,930,1396,39326,41160,1542,47956,1782,4240,2334,2812,23930,31796,650,2208,40586,41640,1174,1664,1710,70624,41202,5248,41454,3260,41482,41984,34842,38140,714,43764,12166,13272,850,1364,42990,45012,1198,43760,1462,47944,1722,2248,38626,44160,802,46936,1582,2740,1430,1968,2018,23212,886,6376,1162,5676,40102,40652,41186,12224,974,2072,2966,4176,1122,1684,4290,6500,41150,34088,41438,11416,42666,43240,11658,26200,786,3616,42218,43480,42050,42636,42690,46292,1074,10052,1374,37836,1406,2004,45786,49712,1050,2608,2650,3964,1210,1820,2802,5200,1234,3948,1546,55148,39738,40360,41782,66576,870,49000,2410,3776,2754,3388,3446,11508,966,32860,1290,9612,41014,41660,42286,10796,41466,2748,2362,3780,41638,42296,5906,8492,41810,4364,42146,8772,35286,35956,38810,189296,1010,44888,12842,14312,1302,1984,2046,9820,1538,46156,1886,45528,1922,2616,48638,53192,1086,3412,39326,40848,1270,1976,47642,50416,1782,3924,2142,8820,2494,3212,23930,31476,1230,7580,1886,3460,40586,41316,41382,64776,1338,13448,1710,70296,3458,4200,4918,107844,41454,2928,5038,6664,41650,42404,34842,37804,43042,12680,43426,10072,12166,12932,26966,112924,1022,4900,42990,44668,42566,43344,43414,12324,1462,47596,1858,46108,1898,2688,38626,43808,1374,3328,46582,48312,1582,2384,3410,6560,1610,5308,2018,22852,3342,4156,6014,64596,1162,5312,2366,4148,40286,41112,41186,11856,1282,67960,1702,6180,2966,3804,4614,43812,1310,4792,4290,6124,1530,2380,33710,37048,41438,11036,41870,7660,42858,43720,11658,25816,1286,4192,3230,5116,42218,43092,43170,12424,42246,9956,42690,45900,42734,43620,9658,15468,1374,37440,39702,41640,1606,2504,45786,49312,1750,15816,2206,30016,2650,3560,10730,20288,1414,47680,2802,4792,2534,3456,3538,28572,1546,54736,2014,50796,39946,40880,41782,66160,2166,3540,48582,50624,2410,3356,4870,8584,2966,10404,3446,11084,24566,25524,32434,196716,1290,9184,2850,4944,41230,42200,42286,10364,1822,66400,2314,46116,2362,3344,71278,77716,41858,5844,5906,8052,42114,43108,3922,7824,42146,8328,42650,139412,35510,36516,38810,188848,1386,14364,44438,46636,12842,13860,13950,27148,1530,114628,2046,9364,43674,44704,45698,18076,1886,45068,44450,46700,2154,3196,48638,52728,2418,47852,2946,16724,39326};
ll getans(ll i){
    if (i<=700) {
        return dp[i];
    }
    else{
        if (i%2==0) {
            return getans(i/2)+i;
        }
        else{
            return getans(i/2*3+2)+i+1;
        }
    }
}
int main(){
    ll n;
    cin>>n;
    cout<<getans(n)<<endl;
}