模拟递归问题。直接递归肯定不行，最容易想到的方法就是用数组模拟。中途遇到了一个问题，就是c++ iostream库的效率问题。用cin >> a >> b >> c时，TLE；换成scanf("%d%d%d", &a, &b, &c)时，AC，时间80ms。status中最前面的都是60ms，看来优化空间不大。关于c库和c++库的输入输出，还有待研

/**
 * @file   zoj1168.c
 * @author  <lox@freelox>
 * @date   Wed May 19 18:59:59 2010
 * 
 * @brief  zoj1168, 模拟问题。直接查表解决。
 * 但是需要注意的是，此题目用scanf系列，AC，时间80ms，用c++的cin流，则TLE，
 * 莫非cin和scanf真有那么大的时间消耗差别？
 */


#include <stdio.h>

int main(int argc, char *argv[])
{
    int w[21][21][21];

    int a, b, c;
    
    for (a = 0; a <= 20; a++)
    {
        for (b = 0; b <= 20; b++)
        {
            for (c = 0; c <= 20; c++)
            {
                if (a == 0 || b == 0 || c == 0)
                {
                    w[a][b][c] = 1;
                }
                else if (a < b && b < c)
                {
                    w[a][b][c] = w[a][b][c-1] + w[a][b-1][c-1] - w[a][b-1][c];
                }
                else
                    w[a][b][c] = w[a-1][b][c] + w[a-1][b-1][c] + w[a-1][b][c-1] - w[a-1][b-1][c-1];
            }
        }
    }

    while (scanf("%d%d%d", &a, &b, &c))
    {
        if (a == -1 && b == -1 && c == -1)
        {
            return 0;
        }
        if (a <= 0 || b <= 0 || c <= 0)
        {
            printf("w(%d, %d, %d) = %d\n",a,b,c,w[0][0][0]);
        }
        else if (a > 20 || b > 20 || c > 20)
        {
            printf("w(%d, %d, %d) = %d\n",a,b,c,w[20][20][20]);
        }
        else
            printf("w(%d, %d, %d) = %d\n",a,b,c,w[a][b][c]);
    }
    
    return 0;
}

毕竟是做题经验不足，开始看题被唬住了。题目大意是给定一个数据a[i]，寻找四个数字i, j, k, m, 使得a[m]=a[i]+a[j]+a[k]，并求出max(a[m])。

最容易想到的是暴力算法。求出每个三元组的和，然后再搜索，复杂度为O(n^3)级别的。但是我觉得应该会有更好的解法，就去百度上查。事实上最终我用的也是这种暴力方法。参考别人代码，结合STL。思路大体上是先排序，然后再二分搜索。最后通过的时间是50ms。看了下本题目的status，前面的高人通过时间都是0ms，由此看来本题肯定有优化的可能。只是我不知道罢了。暂且放下。

STL应用太过生疏，仿函数和函数指针的应用还经常混淆。需要加强。

#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

int main(int argc, char *argv[])
{
    int inta[1000], n, wi;

    while ((cin >> n) && n)
    {
        int i, j, m, u;
        wi = 536870912;
        for (i = 0; i < n; ++i)
        {
            cin >> inta[i];
        }

        sort(inta, inta+n);
        
        if (n < 4)
        {
            goto END;
        }

        for (i = n - 1; i >= 0; i--)
            for (m = n - 1; m >= 0; m--)
            {
                if (i == m)
                {
                    continue;
                }
                for (j = m - 1; j > 0; j--)
                {
                    if (j == i)
                    {
                        continue;
                    }

                    u = inta[i] - inta[m] - inta[j];

                    if (u != inta[i] && u != inta[m] && u != inta[j])
                    {
                        if (binary_search(inta, inta+n, u))
                        {
                            wi = inta[i];
                            goto END;
                        }
                    }
                }
            }
      END:
        if (wi == 536870912)
        {
            cout << "no solution" << endl;
        }
        else
            cout << wi << endl;
    }
    
    return 0;
}

继续刷水题。看到这道题目有印象，想想，ms当初算法是想出来了。就是自己想写个链表却有bug，结果一直拖着没有解决。好歹前几天又研究了下STL，这下派上用场了。不过代码写的很乱，感觉不够优美，不beautiful。最后的输入输出有些小问题，导致第一次提交是Presentation Error。后来仔细看了看搞定。算了，先糊弄着看吧。15道了。还有285道。一道一道的啃。

具体解题思路就不写了。大概如下，如果是P，就进行双层循环，然后搞一个数组的索引（不知道该怎么说哎……）；如果是I，建立一个链表，从Inversion[]的最后一个元素开始循环，然后分别处理每个元素。根据Inversion[i]的数值遍历链表并插入合适的元素。最后的输入输出有问题。仔细看一下就行了。

#include <iostream>
#include <list>
using namespace std;

const int max_size = 50;

int main(int argc, char *argv[])
{
    int cases;
    char method;

    while (1)
    {
        cin >> cases;

        if (cases == 0)
        {
            break;
        }

        cin >> method;
        if (method == 'P')
        {
            int P[max_size], I[max_size];

            for (int i = 0; i < cases; ++i)
            {
                cin >> P[i];
                I[i] = 0;
            }
            for (int i = 0; i < cases; ++i)
            {
                for (int j = i + 1; j < cases; ++j)
                {
                    if (P[i] > P[j])
                    {
                        I[P[j]-1]++;
                    }
                }
            }
            for (int i = 0; i < cases - 1; ++i)
            {
                cout << I[i] << " ";
            }
            cout << I[cases - 1] << endl;
        }
        else if (method == 'I')
        {
            list<int> P;
            int I[max_size];

            for (int i = 0; i < cases; ++i)
            {
                cin >> I[i];
            }

            P.push_back(cases);
                        
            for (int i = cases - 2; i >= 0; --i)
            {
                list<int>::iterator it = P.begin();
                for (int j = 0; j < I[i]; j++)
                {
                    it++;
                }
                P.insert(it, i+1);
            }

            list<int>::iterator it;
            int i;
            
            for (i = 0, it = P.begin(); i < P.size() - 1; ++it, ++i)
            {
                cout << *it << " ";
            }
            
            cout << *it << endl;
        }
        else
        {
            break;
        }
    }
    
    return 0;
}