BabbleDay's Blog

这几天看了Tanky Woo的母函数http://www.wutianqi.com/?p=596，感觉把数学和现实生活真正结合是在ACM里啊～～

我在这里把生成函数的解题思路再整理一下，一是把多项式的计算和物品的组合更直接的关联起来，二是通过举例补充一下Tanky Woo没有细讲的题目。

这是在理解dfs大致意思之后自己写的，一定是不够优雅的，但是觉得很开心～所以刚着手dfs的童鞋也可以试试～

竟然因为使用滚动数组是不小心把1-t写成t-1而debug半个多小时。。。。下次一定要注意。。。。

oj数据输入技巧：若没有输入结束标志，则可使用返回布尔值的init（）来控制输入结束

bool init()
{
    getline(cin, str1);
    m = str1.length();
    if(m==0) return false;
    getline(cin, str2);
    n = str2.length();
    return true;
}

只求子序列的长度的算法：
设str1[1,2,3...m] str2[1,2,3...n]
a[t][m] t是滚动数组标志，遍历str2的所有作为行i
             m是str1的所有，作为列j
所以 a[t][j] = a[1-t][j-1] + 1 when str1[i] == str2[j]
                       max { a[1-t][j] , a[t][j-1] } otherwise

#include <iostream>
#include <string>
#include <cstring>
#define max(a, b) a>b?a:b

using namespace std;

string str1;
string str2;
int m=0;
int n=0;

bool init()
{
    getline(cin, str1);
    m = str1.length();
    if(m==0) return false;
    getline(cin, str2);
    n = str2.length();
    return true;
}

void the_case()
{
    int a[2][m+1];
    memset(a, 0, sizeof(a));
    int t=0;
    for(int i=0; i<n; i++)
    {
        memset(a[t], 0, sizeof(a[t]));
        for(int j=1; j<m+1; j++)
        {
            if(str1.at(j-1) == str2.at(i))
                a[t][j] = a[1-t][j-1] + 1;
            else
                a[t][j] = max( a[t][j-1], a[1-t][j] );
        }
        t = 1-t;
    }
    cout << a[1-t][m] << endl;
}

int main()
{
    while(init())
    {
        the_case();
    }
    return 0;
}

关于使用回溯法重构子序列，有待更新