大疆的一道笔试题目

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

题目描述
爱玩游戏的小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;

}

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