QianYi Ke?
2019-10-19 13:11
采纳率: 93.3%
浏览 184

这是一道本科的编程问题,因为我刚学一年还不大清楚,请问有人愿意解答吗?谢谢

题目要求都在图片里,要求用C++。谢谢

图片说明

  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 邀请回答

2条回答 默认 最新

  • threenewbee 2019-10-20 07:53
    最佳回答
    #include <stdlib.h>
    #include <string.h>
    #include <iostream>
    using namespace std;
    
    int* initdkntor(int n, int * brokens, int m)
    {
        int * p = (int *)malloc(sizeof(int) * n);
        memset(p, 0, sizeof(int) * n);
        for (int i = 0; i < m; i++)
        {
            for (int j = brokens[i * 2] - 1; j < brokens[i * 2 + 1]; j++)
                p[j] = 1;
        }
        return p;
    }
    
    int* tryit(int *seed, int n, int a, int b)
    {
        int * p = (int *)malloc(sizeof(int) * n);
        memcpy(p, seed, sizeof(int) * n);
        for (int i = a - 1; i < b; i++) p[i] = 0;
        return p;
    }
    
    int check(int *p, int n)
    {
        for (int i = 0; i < n; i++) if (p[i]) return 1;
        return 0;
    }
    
    int solve(int *seed, int seedcost, int n, int *sp, int spn)
    {
        if (!check(seed, n)) return seedcost;
        if (!spn) return -1;
        int min = -1;
        for (int i = 0; i < spn; i++)
        {
            int * seed1 = tryit(seed, n, sp[i*3], sp[i*3+1]);
            int cost = solve(seed1, seedcost + sp[i*3+2], n, sp + 3 * (i+1), spn - i-1);
            if (cost != -1)
                if (cost < min || min == -1) min = cost;
        }
        return min;
    }
    
    int main()
    {
        int s;
        int n;
        int m;
        cin >> n >> m >> s;
        int * bk = new int[n * 2];
        for (int i = 0; i < n; i++)
            cin >> bk[i*2] >> bk[i*2+1];
        int * sp = new int[m * 3];
        for (int i = 0; i < m; i++)
            cin >> sp[i*3] >> sp[i*3+1] >> sp[i*3+2];
        int * dkntor = initdkntor(s, bk, n);
        int result = solve(dkntor, 0, s, sp, m);
        cout << result << endl;
        return 0;
    }
    

    在线编译通过
    https://ideone.com/195uxV

    评论
    解决 无用
    打赏 举报
查看更多回答(1条)

相关推荐 更多相似问题