我不太熟悉区间DP,哪位大佬能指点一下?谢谢啦!
查看原帖
我不太熟悉区间DP,哪位大佬能指点一下?谢谢啦!
1740609
lqy202400091楼主2025/7/26 22:44

高精度应该没有问题,问题应该在于DP部分。如果DP部分没有问题也可以说一声,让我再检查一遍高精度。如果方便的话,随便看看高精度部分呗!谢谢大佬们的指点啦!

#include<iostream>
#include<cstdio>
#include<deque>
using std::deque;
const int js = 1e8, w = 8;
class sum {//高精度封装(8至192行)
public:
    deque<unsigned long> s{ 0 };
    unsigned la = 0, ls = 0;

    sum(unsigned long n) :s{n} {}
    sum(sum& a) :s{ a.s } {};
    sum() = default;

    sum operator +  (const sum& a)
    {
        la = a.s.size();
        ls = s.size();
        sum b; b.s = s;
        if (ls < la)
        {
            for (; ls <= la; ++ls)
                b.s.push_front(0);
        }
        for (int i = la - 1, j = ls - 1; i >= 0; --i, --j)
            b.s[j] += a.s[i];
        for (int i = ls - 1; i > 0; --i)
        {
            b.s[i - 1] += b.s[i] / js;
            b.s[i] %= js;
        }
        if (b.s[0] >= js)
        {
            b.s.push_front(b.s[0] / js);
            b.s[1] %= js;
        }
        while (!b.s.empty()&&b.s[0] == 0) b.s.erase(b.s.begin());
        return  b;
    }

    sum operator +  (const int& a)
    {
        sum b;
        ls = s.size();
        b.s = s;
        b.s.back() += a;
        for (int i = ls - 1; i > 0; --i)
        {
            b.s[i - 1] += b.s[i] / js;
            b.s[i] %= js;
        }
        if (b.s[0] >= js)
        {
            b.s.push_front(b.s[0] / js);
            b.s[1] %= js;
        }
        return  b;

    }
    sum& operator += (const sum& a)
    {
        la = a.s.size();
        ls = s.size();
        if (ls < la)
        {
            for (; ls <= la; ++ls)
                s.push_front(0); 
            
        }
        for (int i = la - 1, j = ls - 1; i >= 0; --i, --j)
            s[j] += a.s[i];
        for (int i = ls - 1; i > 0; --i)
        {
            s[i - 1] += s[i] / js;
            s[i] %= js;
        }
        if (s[0] >= js)
        {
            s.push_front(s[0] / js);
            s[1] %= js;
        }
        while (!s.empty()&&s[0] == 0) s.erase(s.begin());
        return  *this;
    }

    sum operator *  (const int& n) 
    {
        ls = s.size();
        sum a;
        a.s = s;
        for (int i = 0; i < ls; ++i)
        {
            a.s[i] *= n;
        }
        for (int i = ls - 1; i > 0; --i)
        {
            a.s[i - 1] += a.s[i] / js;
            a.s[i] %= js;
        }
        if (a.s[0] >= js)
        {
            a.s.push_front(a.s[0] / js);
            a.s[1] %= js;
        }
        return a;
    }

    sum& operator *= (const int& n)
    {
        ls = s.size();
        for (int i = 0; i < ls; ++i)
        {
            s[i] *= n;
        }
        for (int i = ls - 1; i > 0; --i)
        {
            s[i - 1] += s[i] / js;
            s[i] %= js;
        }
        if (s[0] >= js)
        {
            s.push_front(s[0] / js);
            s[1] %= js;
        }
        return *this;
    }

    void operator = (const sum& a)
    {
        s = a.s;
        return;
    }

    void operator = (int& n)
    {
        s.erase(s.begin(), s.end());
        s.push_front(n);
        return;
    }

    bool operator >=  (const sum& a)
    {
        ls = s.size();
        la = a.s.size();
        if (ls > la) return true;
        if (ls < la) return false;
        for (int i = 0; i < ls; ++i)
            if (s[i] < a.s[i])
                return false;
        return true;
    }

    bool operator <= (const sum& a)
    {
        ls = s.size();
        la = a.s.size();
        if (ls < la) return true;
        if (ls > la) return false;
        for (int i = 0; i < ls; ++i)
            if (s[i] > a.s[i])
                return false;
        return true;
    }


    bool operator > (const sum& a)
    {
        ls = s.size();
        la = a.s.size();
        if (ls > la) return true;
        if (ls < la) return false;
        if (s == a.s) return false;
        for (int i = 0; i < ls; ++i)
            if (s[i] < a.s[i])
                return false;
        return true;
    }


    bool operator < (const sum& a) 
    {
        ls = s.size();
        la = a.s.size();
        if (ls > la) return false;
        if (ls < la) return true;
        return s < a.s;
    }

    friend void print(sum& a);
};

void print(sum& a);//用于输出结果。

sum ans, dp[80][80],a,b;
unsigned int n, m,jz[80][80],sj,j;
unsigned long h;

int main()
{
    scanf("%d %d", &n, &m);//输入部分。
    for(int i=0;i<n;++i)
        for (j=0; j < m; ++j)
            scanf("%d", jz[i] + j);
  //DP部分。采用的是从小区间到大区间的思想。
    for (int k = 0; k < n; ++k)
    {
        for (int i = 0; i < m; ++i)
        {
            dp[i][i] = jz[k][i] * 2;
        }
        for (int len = 2; len <= m; ++len)
        {
            sj = m - len + 1;
            for (int i = 0; i < sj; ++i)
            {
                j = i + len - 1;
                a = dp[i][j - 1] + jz[k][j];
                b = dp[i+1][j] + jz[k][i];                
                if (a > b)
                    dp[i][j] = a;
                else dp[i][j] = b;
                dp[i][j] *= 2;
            }
        }
        if(m)
          ans += dp[0][m-1];
    }
    print(ans);
}

void print(sum& a)
{
    h = a.s[0];
    printf("%ld", h);
    n = a.s.size();
    for (int i = 1; i < n; ++i)
    {
        h = a.s[i];
        printf("%0*ld", w, h);
    }
    return;
}

2025/7/26 22:44
加载中...