大疆的一道笔试题目_大疆笔试题库

同学笔试之后告诉我的，感觉这个题目也是动态规划问题，但是没有在笔试环境测试，所以不知道能不能全通过。

题目描述

爱玩游戏的小J，小J给每个游戏标上一个成就值，同时估算了完成这些游戏所需要的时间，现在他只有X天时间，而游戏一旦开始玩，至少需要玩一天才能够停下来，那么他玩完的游戏的成就值之和最大能达到多少呢？

输入：
第一行输入case数T，对于每个case，第一行输入游戏的数目N，总时间X。从第二行到第N+1行输入游戏的成就值Ai，所需要的时间Bi。

输出：
对每个case输出一行，成就值之和的最大值。

例如：
输入：
2
2 2
10 1
20 2
3 4
10 2
18 3
10 2

输出：
20
20
#思路

这个是一个典型的动态规划问题，利用一个与天数相同长度的矩阵代表每天能够达到的最大成就值，然后取这个矩阵的back（），就代表最后所要的X天的最大成就值，思路和上一次中兴笔试的那个动态规划感觉差不多。

#code

  

    #include<iostream>
    #include<vector>
    #include<algorithm>
    #include<map>
    using namespace std;
    int value(vector<pair<int,int>>&a,int day)
    {
        vector<int>p(day+1,0);
        for (int k = 0; k<a.size();++k)
        {
            for(int i=day;i>=0;--i)
            {
                if(a[k].second<=i)
                    p[i]=max(p[i],p[i-a[k].second]+a[k].first);
            }
        }
        return p.back();
    
    }
    int main()
    {
        int num=0;
        cin>>num;
        vector<int>res;
        while(num--)
        {
            int game_num=0;
            cin>>game_num;
            int day_num=0;
            cin>>day_num;
            vector<pair<int,int>>game__num;
            while(game_num--)
            {    
                pair<int,int> temp;
                cin>>temp.first;
                cin>>temp.second;
                game__num.push_back(temp);
            }
            int value_num=value(game__num,day_num);
            res.push_back(value_num);
        }
        for(int i=0;i<res.size();++i)
        {
            cout<<res[i]<<endl;
        }
        system("pause");
        return 0;
         
    }

运行结果和示例相同，但是因为没有参加笔试，所以不知道通过率会是多少。