weixin_45808101
这个呢称很难改
2019-11-10 10:23
采纳率: 0%
浏览 312

用c语言的题目,应该怎么编。

话说,韩信将军神机妙算,兵法娴熟,武艺超群,同时还是一位独具慧眼的将军,能够一眼看出士兵的武艺值 X。一次执行任务,韩信将军到校场点兵,已知校场一共有N位士兵,士兵们的武艺值高低不齐。

随军主簿说一共要选M位士兵,并且要满足所挑选士兵的武艺值 X 依次严格递增。(从第一名士兵开始选,可以选也可以不选,只要满足武艺值递增且人数满足M就算一种方案。)

韩信将军眯了眯眼睛,立即说出了所有可能选择方案数。
    数据范围: 1 <= M <= N <= 1000 ,每一个士兵的武艺值 X ( 1 <= X <= 10^9)

输入
第一行输入一个正整数num,代表一共有num组测试数据。( 1 <= num <= 100)

对于每组数据,第一行包含两个整数N和M,N代表士兵总数,M代表挑选的士兵数。

第二行包含N个整数,表示士兵的武艺值X。
    输出
每组数据输出一个结果,每个结果占一行。

输出格式为“Answer #a: b”,a为数据组别序号,从1开始,b为结果。

由于数据可能很大,请你输入对 10^9+10 取模后的结果。
  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

3条回答 默认 最新

  • dabocaiqq
    dabocaiqq 2019-11-10 10:28
    点赞 评论
  • Africa_South
    Wayward:) 2019-11-10 11:16

    是只求出一种可能方案?那输出的b是什么?

    点赞 评论
  • qq_28062895
    qq_28062895 2019-11-10 13:59

    可以用C++来编写这个程序吗?

    #include<bits/stdc++.h>
    using namespace std;
    void solve()
    {
        long long dp[1005][1005],X[1005],N,M;
        cin>>N>>M;
        for(int i=1;i<=N;i++)
        {
            cin>>X[i];
        }
        for(int in=0;in<=N;in++)
        {
            for(int im=0;im<=M;im++)
            {
                dp[in][im]=0;
            }
        }
        dp[0][0]=1;
        for(int i=1;i<=N;i++)
        {
            for(int in=0;in<=N;in++)
            {
                for(int im=1;im<=M;im++)
                {
                    if(in-X[i]>0)
                        dp[in][im]+=dp[in-X[i]][im-1];
                }
            }
        }
        cout<<dp[N][M]%1000000010;
    }
    
    int main()
    {
        int num;
        cin>>num;
        for(int i=1;i<=num;i++)
        {
            cout<<"Answer #"<<i<<':';
            solve();
            cout<<endl;
        }
        return 0;
    }
    //一个很水的三维dp题目,第三维应该使用滚动数组。 
    
    点赞 评论

相关推荐