shiro

链表分割为递增的子序列的划分方法
现给出一个单链表,每个结点包含的数据是一个数字Num (0 <= Num <= 100)。将该链表切割...
扫描右侧二维码阅读全文
27
2018/05

链表分割为递增的子序列的划分方法

现给出一个单链表,每个结点包含的数据是一个数字Num (0 <= Num <= 100)。将该链表切割成连续的若干段,使得每一段中的元素之和严格递增。链表上的元素不超过50个。请编程求出有多少种不同的切割方法。

输入格式:

第一行给出链表第一个结点的地址H和要给出的结点总个数N。其中H用4位整数表示,N为不大于100的正整数。 之后N行,每行按如下格式给出结点信息:

Address Data Next

Address为结点地址,Data为数字Num,Next为下一个结点的地址,格式同H;当Next的值为-1时,表示该结点没有下一个结点,遍历结束。

输出格式:

在一行中输出切割方法数。

输入样例:

0001 3
0001 1 0030
0030 2 0812
0812 4 -1

输出样例:

4

样例解释:

有4种切割法方法:
1和2,4
1,2和4
1,2,4
不切割,整个链表作为一段。

#include<iostream>
#include <vector>

class Node{
public:
    int num;
    int next;
    Node() : num(-1), next(-1){}
};
Node set[10000];
long long int item = 0;
std::vector<int> V;
void dfs(int index, int sum){
    if(index == -1)
        return ;
    int s = 0;
    int pos = index;
    while(pos != -1){
        s += set[pos].num;
        if(s > sum)
            dfs(set[pos].next, s);
        pos = set[pos].next;
    }
    if(s > sum)
        item++;
}

int main(){
    int h, n, a, num, next;

    std::cin >> h >> n;
    for (int i = 0; i < n; ++i) {
        std::cin >> a >> num >> next;
        set[a].num = num;   set[a].next = next;
    }
    dfs(h, 0);
    std::cout << item;
}
Last modification:August 27th, 2018 at 02:38 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment