给定条件下，如何最大化达成目的？

    好久没有更新博客了，主要是懒得写了，今天闲来无事，在题库发芽网上看到一个算法题，于是就思考了一下。

题目：

---

原文：

If you can only press the keyboard for N times and you are only allowed to
press four types of keys, namely, 'A','CTRL+C','CTRL+V','CTRL+A', write
a program to produce the maximum numbers of A and also print out the
sequence of keys.

译文：

（假定你在记事本或任何windows下的文字处理软件中，以空文本开始。）如果你只能输入
N 个按键（或组合），允许的按键只有“A”、“CTRL+C”（复制选定文本到剪贴板）、 “CTRL+V”（粘贴剪贴板文本到光标处）、“CTRL+A”（选择全部文本）四种。

写个程序生成产生最多 A 的按键序列。

---

一开始看到这个题目，首先想到的就是利用归纳法。这里为了简单，我只是求出最长的按键序列的长度，比如这里我们需要求N个按键的序列的长度，这里用f(n)表示。
假设我们已经知道了前N-1个按键序列的长度。那么，要求N个按键的序列长度，有以下几种情况：
1）第N个按键是"A"，那么序列长度f(n) = f(n-1)+1。
2）如果在第N个按键前已经有过“CTRL+A”、“CTRL+C”和“CTRL+V”操作，这里拷贝到"A"的长度是paste_num。那么第N个按键是“CTRL+V”。此时的序列长度就是f(n)=f(n-1)+paste_num。
3）最后三个按键的操作是“CTRL+A”、“CTRL+C”和“CTRL+V”。那么此时的序列长度就是f(n)=f(n-3)×2。
我们只要比较这三种情况，然后选取长度最大的那一种即可。
c语言实现时，采用一个3个元素的数组保存n的前三项的值，数组初始化为1，2，3。因为当按键次数小于4的时候，每次按键都是“A”。代码如下：

#include <stdio.h>

#define max(a,b) ((a) > (b) ? (a) : (b))

int a[3]={1,2,3};
int paste = 0;        /*是否已经进行了复制，0表示否*/
int paste_num = 0;    /*缓冲区中A的数量*/

int xmax2(int a, int b)
{
    if (a <= b)
    {
        paste = 1;
        paste_num = b/2;
        return b;
    }
    return a;
}

int xmax3(int a, int b, int c)
{
    int max2 = max(a, b);
    int maxall = max(max2, c);
    if (maxall == c)
    {
        paste_num = c/2;/*更新缓冲区中"A"的数量*/
    }
    return maxall;
}

int f(int n)
{
    int i=0;
    for (i=3; i<n; i++)
    {
        if (paste == 0)/*尚未进行复制操作*/
        {
            a[i%3] = xmax2(a[(i-1)%3]+1, a[(i-3)%3]*2);
        }
        else
            a[i%3] = xmax3(a[(i-1)%3]+1, a[(i-1)%3]+paste_num, a[(i-3)%3]*2);
    }
    return a[(n-1)%3];
}

int main()
{
    printf("%d %d\n", 7, f(7));
    return 0;
}