大疆 8.6 软开B卷

大疆 先贴代码，题目在后面

第一题  爱玩游戏的小J  简单的背包问题

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int T;
    cin >> T;
    for(int i=0; i<T; i++){
        int N, X;
        cin >> N >> X;
        vector<int> dp(X+1, 0);
        vector<int> val(N, 0);
        vector<int> tim(N, 0);
        for(int i=0; i<N; i++){
            cin >> val[i] >> tim[i];
            for(int j=X; j>=0 && j>= tim[i]; j--)
                dp[j] = max(dp[j], dp[j-tim[i]] + val[i]); 
        }
        cout << dp[X] << endl;
    }
    return 0;
}

第二题 不听话的机器人  直接hashMap即可

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main(){
    int N, M;
    while(cin >> N >> M){
        unordered_map<string, string> hashMap;
        for(int i=0; i<N; i++){
            string str1, str2;
            cin >> str1 >> str2;
            hashMap[str1] = str2;
        }

        for(int i=0; i<M; i++){
            string str;
            cin >> str;
            cout << hashMap[str] << endl;
        }
    }
    return 0;
}

第三题  应该怎么吃呢

暴力递归，过了 50%
不过直接输出 1，也是 50% 手动捂脸

#include <iostream>
#include <vector>
#include <algorithm> 
using namespace std;

int mode = 1e9+7;

void dfs(vector<int> &arr, int &res, int val, int st, int last){
    if(val == 0) {
        res = (res+1) % mode;
        return ;
    }
    if(val < 0 || st >= arr.size()) return ;

    for(int i=min(last-1, val/arr[st]); i>=0; i--)
        dfs(arr, res, val-arr[st]*i, st+1, i);

}

int main(){
    int V, N, M;
    while(cin >> V >> N){
        // 每件物品的价值
        vector<int> arr(N);
        // 喜爱程度，越小越喜爱
        vector<int> brr(N, N);
        for(int i=0; i<N; i++)
            cin >> arr[i];

        cin >> M;
        for(int i=0; i<M; i++){
            int tem;
            cin >> tem;
            brr[tem-1] = i;
        }
        sort(arr.begin(), arr.end(), [&](int a, int b){ 
            return brr[a] < brr[b]; });

        int res = 0;
        dfs(arr, res, V, 0, V);
        cout << res << endl;

    }
    return 0;
}