計算機二級考試C++輔導(dǎo)：usaco4.3BuyLow,BuyLower動態(tài)規(guī)劃

典型的動態(tài)規(guī)劃，難點是第二步，cnt[i]表示以a[i]結(jié)尾的最長下降序列的種數(shù)，則
    cnt[i] = count( len[k]+1==len[i]), 1<=k < i ， 其中l(wèi)en[i]表示以a[i]結(jié)尾的最長下降子序列長度
    還有一個問題，如果生成的實際序列值相等，則算作一種，可以通過一下方法處理：
    計算出a[i]之后和第一個和a[i]相等的數(shù)a[k]，令next[i] = k; 如果沒有相等的則next[i] = 0
    計數(shù)時如果 next[j]!=0 && next[j] < i ，則不累計，因為位于j和i之間的數(shù)里存在和a[i]相等的，從而可以以a[next[j]]替換a[j]來得
    到相同的序列；同時，累加的過程是指數(shù)級增長的，所以要用高精度
    /*
    PROG: buylow
    LANG: C++
    ID: heben991
    */
    #include
    #include
    using namespace std;
    const int N = 6000, R = 10000, L = 250;
    int len[N], a[N], next[N];
    struct bignum
    {
    int a[L];
    int n;
    bignum operator = (int b)
    {
    memset(a,0,sizeof(a));
    n = 1;
    a[1] = b;
    }
    bignum operator = (const bignum &b)
    {
    memset(a,0,sizeof(a));
    for(int i = 1; i <= b.n; ++i) a[i] = b.a[i];
    n = b.n;
    }
    void print()
    {
    int i;
    printf("%d", a[n]);
    for(i = n-1; i >= 1; --i) printf("%04d", a[i]);
    }