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

典型的動(dòng)態(tài)規(guī)劃，難點(diǎn)是第二步，cnt[i]表示以a[i]結(jié)尾的最長(zhǎng)下降序列的種數(shù)，則
    cnt[i] = count( len[k]+1==len[i]), 1<=k < i ， 其中l(wèi)en[i]表示以a[i]結(jié)尾的最長(zhǎng)下降子序列長(zhǎng)度
    還有一個(gè)問(wèn)題，如果生成的實(shí)際序列值相等，則算作一種，可以通過(guò)一下方法處理：
    計(jì)算出a[i]之后和第一個(gè)和a[i]相等的數(shù)a[k]，令next[i] = k; 如果沒(méi)有相等的則next[i] = 0
    計(jì)數(shù)時(shí)如果 next[j]!=0 && next[j] < i ，則不累計(jì)，因?yàn)槲挥趈和i之間的數(shù)里存在和a[i]相等的，從而可以以a[next[j]]替換a[j]來(lái)得
    到相同的序列；同時(shí)，累加的過(guò)程是指數(shù)級(jí)增長(zhǎng)的，所以要用高精度
    /*
    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]);
    }