[已解决]求教怎么用vector实现数塔问题

狂野的小黄花

/*因为最近在学STL库，所以想用vector代替二维数组实现数塔问题
输入如下
5
5
8 3
12 7 16
4 10 11 6
9 5 3 9 4
输出如下
44

输入倒是可以正常输入  输出不出来程序直接退出了 大佬们帮忙看看吧QAQ（我知道二维数组就可以实现，就是想知道vector能不能这样用解决问题）
*/
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,temp;
    cin>>n;
    vector<vector<int> > f(n+1);
    vector<vector<int> > dp(n+1);
    vector<int> v(n+1);
    for(int i=1;i<=n;i++){
            v.clear();
        for(int j=1;j<=i;j++){
            cin>>temp;
            v.push_back(temp);
        }
        f.push_back(v);
    }
    for(int j=1;j<=n;j++){
        dp[n][j]=f[n][j];
    }
    for(int i=n-1;i>=1;i++){
        for(int j=1;j<=i;j++)
        {

            dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j];
        }
    }
    cout<<dp[1][1]<<endl;
    return 0;
}

最佳答案

月排行榜 / 总排行榜

人造人

2021-3-31 18:34:21

你的这个算法参考的哪个教程？我有点看不懂你的这个算法，我需要先去看一看你这个算法的实现思路，因为你的代码没有注释，^_^
我用vector写了4个版本，两个递归的和两个非递归的，同样没有注释，^_^
我参考了这个教程，如果要理解我写的这些代码，可以先去看一下这篇文章
https://blog.csdn.net/theonegis/article/details/45801201

#include <iostream>
#include <memory>
#include <vector>

struct data_tower_t {
    ssize_t data;
    std::shared_ptr<data_tower_t> lchild;
    std::shared_ptr<data_tower_t> rchild;
    std::shared_ptr<data_tower_t> rsibling;
};

const std::vector<std::shared_ptr<data_tower_t>> get_data(std::istream &is, size_t size) {
    std::vector<std::shared_ptr<data_tower_t>> result;
    ssize_t data;
    for(size_t i = 0; i < size; ++i) {
        if(is >> data) {
            std::shared_ptr<data_tower_t> n = std::make_shared<data_tower_t>();
            n->data = data;
            result.push_back(n);
        } else if(i == 0) return result;
        else throw "输入数据错误";
    }
    return result;
}

const std::shared_ptr<data_tower_t> create_data_tower(std::istream &is) {
    std::shared_ptr<data_tower_t> result;
    std::shared_ptr<data_tower_t> p, q;
    for(size_t i = 1; ; ++i) {
        std::vector<std::shared_ptr<data_tower_t>> v = get_data(is, i);
        if(v.empty()) return result;
        for(auto iter = v.begin(); iter != v.end() - 1; ++iter) (*iter)->rsibling = *(iter + 1);
        if(i == 1) p = result = v[0];
        else {
            q = p;
            for(auto iter = v.begin(); iter != v.end(); ++iter) {
                if(!q->lchild) q->lchild = *iter;
                else {
                    q->rchild = *iter;
                    q = q->rsibling;
                    if(q) q->lchild = *iter;
                }
            }
            p = p->lchild;
        }
    }
    return result;
}

ssize_t get_sum(const std::vector<ssize_t> &v) {
    ssize_t sum = 0;
    for(const auto &i: v) sum += i;
    return sum;
}

const std::vector<ssize_t> get_path(const std::shared_ptr<data_tower_t> &d) {
    if(d->lchild == nullptr && d->rchild == nullptr) return std::vector<ssize_t>({d->data});
    std::vector<ssize_t> lv = get_path(d->lchild);
    std::vector<ssize_t> rv = get_path(d->rchild);
    std::vector<ssize_t> *mv = get_sum(lv) > get_sum(rv) ? &lv : &rv;
    mv->insert(mv->begin(), d->data);
    return *mv;
}

std::ostream &operator<<(std::ostream &os, const std::vector<ssize_t> &rhs) {
    for(const auto &i: rhs) os << i << " ";
    return os;
}

int main() {
    std::shared_ptr<data_tower_t> data_tower = create_data_tower(std::cin);
    std::cout << get_path(data_tower) << std::endl;
    return 0;
}

#include <iostream>
#include <memory>
#include <vector>

struct data_tower_t {
    ssize_t data;
    std::shared_ptr<data_tower_t> lchild;
    std::shared_ptr<data_tower_t> rchild;
    std::shared_ptr<data_tower_t> rsibling;
};

const std::vector<std::shared_ptr<data_tower_t>> get_data(std::istream &is, size_t size) {
    std::vector<std::shared_ptr<data_tower_t>> result;
    ssize_t data;
    for(size_t i = 0; i < size; ++i) {
        if(is >> data) {
            std::shared_ptr<data_tower_t> n = std::make_shared<data_tower_t>();
            n->data = data;
            result.push_back(n);
        } else if(i == 0) return result;
        else throw "输入数据错误";
    }
    return result;
}

const std::shared_ptr<data_tower_t> create_data_tower(std::istream &is) {
    std::shared_ptr<data_tower_t> result;
    std::shared_ptr<data_tower_t> p, q;
    for(size_t i = 1; ; ++i) {
        std::vector<std::shared_ptr<data_tower_t>> v = get_data(is, i);
        if(v.empty()) return result;
        for(auto iter = v.begin(); iter != v.end() - 1; ++iter) (*iter)->rsibling = *(iter + 1);
        if(i == 1) p = result = v[0];
        else {
            q = p;
            for(auto iter = v.begin(); iter != v.end(); ++iter) {
                if(!q->lchild) q->lchild = *iter;
                else {
                    q->rchild = *iter;
                    q = q->rsibling;
                    if(q) q->lchild = *iter;
                }
            }
            p = p->lchild;
        }
    }
    return result;
}

ssize_t get_max(const std::shared_ptr<data_tower_t> &d) {
    if(d->lchild == nullptr && d->rchild == nullptr) return d->data;
    ssize_t ls = get_max(d->lchild);
    ssize_t rs = get_max(d->rchild);
    ssize_t ms = ls > rs ? ls : rs;
    return ms + d->data;
}

int main() {
    std::shared_ptr<data_tower_t> data_tower = create_data_tower(std::cin);
    std::cout << get_max(data_tower) << std::endl;
    return 0;
}

#include <iostream>
#include <vector>

const std::vector<ssize_t> get_line_data(std::istream &is, size_t size) {
    std::vector<ssize_t> result;
    ssize_t data;
    for(size_t i = 0; i < size; ++i) {
        if(is >> data) {
            result.push_back(data);
        } else if(i == 0) return result;
        else throw "输入数据错误";
    }
    return result;
}

const std::vector<std::vector<ssize_t>> create_data_tower(std::istream &is) {
    std::vector<std::vector<ssize_t>> result;
    for(size_t i = 1; ; ++i) {
        std::vector<ssize_t> v = get_line_data(is, i);
        if(v.empty()) return result;
        result.push_back(v);
    }
    return result;
}

ssize_t get_sum(const std::vector<ssize_t> &v) {
    ssize_t sum = 0;
    for(const auto &i: v) sum += i;
    return sum;
}

const std::vector<ssize_t> get_path(const std::vector<std::vector<ssize_t>> &d) {
    std::vector<std::vector<ssize_t>> p((d.end() - 1)->size());
    for(size_t i = d.size() - 1; i > 0; --i) {
        std::vector<std::vector<ssize_t>> c(d[i - 1].size());
        for(size_t j = 0; j < c.size(); ++j) {
            if(j == 0) p[j].insert(p[j].begin(), d[i][j]);
            p[j + 1].insert(p[j + 1].begin(), d[i][j + 1]);
            ssize_t ls = get_sum(p[j]);
            ssize_t rs = get_sum(p[j + 1]);
            c[j] = ls > rs ? p[j] : p[j + 1];
        }
        p = c;
    }
    p[0].insert(p[0].begin(), d[0][0]);
    return p[0];
}

std::ostream &operator<<(std::ostream &os, const std::vector<ssize_t> &rhs) {
    for(const auto &i: rhs) os << i << " ";
    return os;
}

int main() {
    std::vector<std::vector<ssize_t>> data_tower = create_data_tower(std::cin);
    std::cout << get_path(data_tower) << std::endl;
    return 0;
}

#include <iostream>
#include <vector>

const std::vector<ssize_t> get_line_data(std::istream &is, size_t size) {
    std::vector<ssize_t> result;
    ssize_t data;
    for(size_t i = 0; i < size; ++i) {
        if(is >> data) {
            result.push_back(data);
        } else if(i == 0) return result;
        else throw "输入数据错误";
    }
    return result;
}

const std::vector<std::vector<ssize_t>> create_data_tower(std::istream &is) {
    std::vector<std::vector<ssize_t>> result;
    for(size_t i = 1; ; ++i) {
        std::vector<ssize_t> v = get_line_data(is, i);
        if(v.empty()) return result;
        result.push_back(v);
    }
    return result;
}

ssize_t get_max(const std::vector<std::vector<ssize_t>> &d) {
    std::vector<ssize_t> p((d.end() - 1)->size());
    for(size_t i = d.size() - 1; i > 0; --i) {
        std::vector<ssize_t> c(d[i - 1].size());
        for(size_t j = 0; j < c.size(); ++j) {
            ssize_t ls = p[j] + d[i][j];
            ssize_t rs = p[j + 1] + d[i][j + 1];
            c[j] = ls > rs ? ls : rs;
        }
        p = c;
    }
    return p[0] + d[0][0];
}

int main() {
    std::vector<std::vector<ssize_t>> data_tower = create_data_tower(std::cin);
    std::cout << get_max(data_tower) << std::endl;
    return 0;
}

跳转到最佳答案楼层

人造人

你的这个算法参考的哪个教程？我有点看不懂你的这个算法，我需要先去看一看你这个算法的实现思路，因为你的代码没有注释，^_^
我用vector写了4个版本，两个递归的和两个非递归的，同样没有注释，^_^
我参考了这个教程，如果要理解我写的这些代码，可以先去看一下这篇文章
https://blog.csdn.net/theonegis/article/details/45801201

#include <iostream>
#include <memory>
#include <vector>

struct data_tower_t {
    ssize_t data;
    std::shared_ptr<data_tower_t> lchild;
    std::shared_ptr<data_tower_t> rchild;
    std::shared_ptr<data_tower_t> rsibling;
};

const std::vector<std::shared_ptr<data_tower_t>> get_data(std::istream &is, size_t size) {
    std::vector<std::shared_ptr<data_tower_t>> result;
    ssize_t data;
    for(size_t i = 0; i < size; ++i) {
        if(is >> data) {
            std::shared_ptr<data_tower_t> n = std::make_shared<data_tower_t>();
            n->data = data;
            result.push_back(n);
        } else if(i == 0) return result;
        else throw "输入数据错误";
    }
    return result;
}

const std::shared_ptr<data_tower_t> create_data_tower(std::istream &is) {
    std::shared_ptr<data_tower_t> result;
    std::shared_ptr<data_tower_t> p, q;
    for(size_t i = 1; ; ++i) {
        std::vector<std::shared_ptr<data_tower_t>> v = get_data(is, i);
        if(v.empty()) return result;
        for(auto iter = v.begin(); iter != v.end() - 1; ++iter) (*iter)->rsibling = *(iter + 1);
        if(i == 1) p = result = v[0];
        else {
            q = p;
            for(auto iter = v.begin(); iter != v.end(); ++iter) {
                if(!q->lchild) q->lchild = *iter;
                else {
                    q->rchild = *iter;
                    q = q->rsibling;
                    if(q) q->lchild = *iter;
                }
            }
            p = p->lchild;
        }
    }
    return result;
}

ssize_t get_sum(const std::vector<ssize_t> &v) {
    ssize_t sum = 0;
    for(const auto &i: v) sum += i;
    return sum;
}

const std::vector<ssize_t> get_path(const std::shared_ptr<data_tower_t> &d) {
    if(d->lchild == nullptr && d->rchild == nullptr) return std::vector<ssize_t>({d->data});
    std::vector<ssize_t> lv = get_path(d->lchild);
    std::vector<ssize_t> rv = get_path(d->rchild);
    std::vector<ssize_t> *mv = get_sum(lv) > get_sum(rv) ? &lv : &rv;
    mv->insert(mv->begin(), d->data);
    return *mv;
}

std::ostream &operator<<(std::ostream &os, const std::vector<ssize_t> &rhs) {
    for(const auto &i: rhs) os << i << " ";
    return os;
}

int main() {
    std::shared_ptr<data_tower_t> data_tower = create_data_tower(std::cin);
    std::cout << get_path(data_tower) << std::endl;
    return 0;
}

#include <iostream>
#include <memory>
#include <vector>

struct data_tower_t {
    ssize_t data;
    std::shared_ptr<data_tower_t> lchild;
    std::shared_ptr<data_tower_t> rchild;
    std::shared_ptr<data_tower_t> rsibling;
};

const std::vector<std::shared_ptr<data_tower_t>> get_data(std::istream &is, size_t size) {
    std::vector<std::shared_ptr<data_tower_t>> result;
    ssize_t data;
    for(size_t i = 0; i < size; ++i) {
        if(is >> data) {
            std::shared_ptr<data_tower_t> n = std::make_shared<data_tower_t>();
            n->data = data;
            result.push_back(n);
        } else if(i == 0) return result;
        else throw "输入数据错误";
    }
    return result;
}

const std::shared_ptr<data_tower_t> create_data_tower(std::istream &is) {
    std::shared_ptr<data_tower_t> result;
    std::shared_ptr<data_tower_t> p, q;
    for(size_t i = 1; ; ++i) {
        std::vector<std::shared_ptr<data_tower_t>> v = get_data(is, i);
        if(v.empty()) return result;
        for(auto iter = v.begin(); iter != v.end() - 1; ++iter) (*iter)->rsibling = *(iter + 1);
        if(i == 1) p = result = v[0];
        else {
            q = p;
            for(auto iter = v.begin(); iter != v.end(); ++iter) {
                if(!q->lchild) q->lchild = *iter;
                else {
                    q->rchild = *iter;
                    q = q->rsibling;
                    if(q) q->lchild = *iter;
                }
            }
            p = p->lchild;
        }
    }
    return result;
}

ssize_t get_max(const std::shared_ptr<data_tower_t> &d) {
    if(d->lchild == nullptr && d->rchild == nullptr) return d->data;
    ssize_t ls = get_max(d->lchild);
    ssize_t rs = get_max(d->rchild);
    ssize_t ms = ls > rs ? ls : rs;
    return ms + d->data;
}

int main() {
    std::shared_ptr<data_tower_t> data_tower = create_data_tower(std::cin);
    std::cout << get_max(data_tower) << std::endl;
    return 0;
}

#include <iostream>
#include <vector>

const std::vector<ssize_t> get_line_data(std::istream &is, size_t size) {
    std::vector<ssize_t> result;
    ssize_t data;
    for(size_t i = 0; i < size; ++i) {
        if(is >> data) {
            result.push_back(data);
        } else if(i == 0) return result;
        else throw "输入数据错误";
    }
    return result;
}

const std::vector<std::vector<ssize_t>> create_data_tower(std::istream &is) {
    std::vector<std::vector<ssize_t>> result;
    for(size_t i = 1; ; ++i) {
        std::vector<ssize_t> v = get_line_data(is, i);
        if(v.empty()) return result;
        result.push_back(v);
    }
    return result;
}

ssize_t get_sum(const std::vector<ssize_t> &v) {
    ssize_t sum = 0;
    for(const auto &i: v) sum += i;
    return sum;
}

const std::vector<ssize_t> get_path(const std::vector<std::vector<ssize_t>> &d) {
    std::vector<std::vector<ssize_t>> p((d.end() - 1)->size());
    for(size_t i = d.size() - 1; i > 0; --i) {
        std::vector<std::vector<ssize_t>> c(d[i - 1].size());
        for(size_t j = 0; j < c.size(); ++j) {
            if(j == 0) p[j].insert(p[j].begin(), d[i][j]);
            p[j + 1].insert(p[j + 1].begin(), d[i][j + 1]);
            ssize_t ls = get_sum(p[j]);
            ssize_t rs = get_sum(p[j + 1]);
            c[j] = ls > rs ? p[j] : p[j + 1];
        }
        p = c;
    }
    p[0].insert(p[0].begin(), d[0][0]);
    return p[0];
}

std::ostream &operator<<(std::ostream &os, const std::vector<ssize_t> &rhs) {
    for(const auto &i: rhs) os << i << " ";
    return os;
}

int main() {
    std::vector<std::vector<ssize_t>> data_tower = create_data_tower(std::cin);
    std::cout << get_path(data_tower) << std::endl;
    return 0;
}

#include <iostream>
#include <vector>

const std::vector<ssize_t> get_line_data(std::istream &is, size_t size) {
    std::vector<ssize_t> result;
    ssize_t data;
    for(size_t i = 0; i < size; ++i) {
        if(is >> data) {
            result.push_back(data);
        } else if(i == 0) return result;
        else throw "输入数据错误";
    }
    return result;
}

const std::vector<std::vector<ssize_t>> create_data_tower(std::istream &is) {
    std::vector<std::vector<ssize_t>> result;
    for(size_t i = 1; ; ++i) {
        std::vector<ssize_t> v = get_line_data(is, i);
        if(v.empty()) return result;
        result.push_back(v);
    }
    return result;
}

ssize_t get_max(const std::vector<std::vector<ssize_t>> &d) {
    std::vector<ssize_t> p((d.end() - 1)->size());
    for(size_t i = d.size() - 1; i > 0; --i) {
        std::vector<ssize_t> c(d[i - 1].size());
        for(size_t j = 0; j < c.size(); ++j) {
            ssize_t ls = p[j] + d[i][j];
            ssize_t rs = p[j + 1] + d[i][j + 1];
            c[j] = ls > rs ? ls : rs;
        }
        p = c;
    }
    return p[0] + d[0][0];
}

int main() {
    std::vector<std::vector<ssize_t>> data_tower = create_data_tower(std::cin);
    std::cout << get_max(data_tower) << std::endl;
    return 0;
}

人造人

我看懂了，思路用的就是我上面那篇文章中提到的方法
代码改动的地方有点多，你一行一行的对代码吧

/*因为最近在学STL库，所以想用vector代替二维数组实现数塔问题
  输入如下
  5
  5
  8 3
  12 7 16
  4 10 11 6
  9 5 3 9 4
  输出如下
  44

  输入倒是可以正常输入  输出不出来程序直接退出了 大佬们帮忙看看吧QAQ（我知道二维数组就可以实现，就是想知道vector能不能这样用解决问题）
  */
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,temp;
    cin>>n;
    vector<vector<int> > f;
    vector<vector<int> > dp(n);
    vector<int> v;
    for(int i=1;i<=n;i++){
        v.clear();
        for(int j=1;j<=i;j++){
            cin>>temp;
            v.push_back(temp);
        }
        f.push_back(v);
    }
    dp[n - 1] = f[n - 1];
    for(int i = 0; i < n - 1; ++i) {
        for(int j = 0; j <= i; ++j) {
            dp[i].resize(j + 1);
        }
    }
    for(int i = n - 2; i >= 0; i--){
        for(int j = 0; j <= i; j++)
        {
            dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + f[i][j];
        }
    }
    cout<<dp[0][0]<<endl;
    return 0;
}

狂野的小黄花

人造人 发表于 2021-3-31 18:34
你的这个算法参考的哪个教程？我有点看不懂你的这个算法，我需要先去看一看你这个算法的实现思路，因为你的 ...

太感谢大佬了！看完你的代码对vector有一定了解了

人造人

数据结构中确实说 数数从1开始，但是在编程中绝大多数情况都是从0开始
如果你在数据结构编程的时候从1开始，你就要非常非常的小心，因为一不小心就弄错边界了
所以还是建议数数从0开始，即使是数据结构编程的时候，这样就绝对不会弄错边界了