8.27 滴滴 tnl

第一题 算式转移

没太了解规则，感觉可能是 遇到连乘或者连加需要重新排序，写了段代码能跑通测试用例，提交 27%
输入输出都调半天

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

int main() 
{ 
    int n;
    cin >> n;
    string str="";
    getline(cin, str);
    getline(cin, str);
    vector<int> num;
    vector<char> sym;
    int ind = -1, len = str.length();
    while(ind < len) {
        int tem = 0;
        char ch = 'o';
        bool flag = true;
        if(str[ind + 1] == '-')
            flag = false, ind++;

        while(++ind < len && str[ind] != ' ')
            tem = tem * 10 + str[ind] - '0';

        if(flag) num.push_back(tem);
        else num.push_back(-tem);
        if(ind == len) break;
        ind++;
        ch = str[ind++];
        sym.push_back(ch);
    }
    for(int i=0; i<n-1; i++) {
        if(sym[i] == '-' || sym[i] == '/') continue;
        int en = i;
        if(sym[i] == '*') {
            while(++en < n-1 && sym[en] == '*') ;
            en++;
        }
        else if(sym[i] == '+') 
            while(++en < n-1 && sym[en] == '+') ;

        vector<int> arr(num.begin()+i, num.begin()+en);
        sort(arr.begin(), arr.end());
        for(int j=i; j<en; j++)
            num[j] = arr[j-i];

        i = --en;

    }
    string res = "";
    for(int i=0; i<n-1; i++)
        res = res + to_string(num[i]) + " " + sym[i] + " ";
    res = res + to_string(num.back());
    cout << res << endl;
    return 0; 
}

第二题 序列移除

这个题目太难理解了，读了半天。。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define INF 0x3f3f3f

int main() {
    int n, total, cost, tot;
    cin >> n >> total >> cost;

    tot = total / cost;

    vector<vector<int>> dp(n+1, vector<int>(tot + 1, INF));
    dp[0][0] = 0;
    vector<int> arr(n+1), brr(n+1);

    for (int i=1; i<=n; i++) cin >> arr[i];
    for (int i=1; i<=n; i++) cin >> brr[i];
    int res = 0, iMax = *max_element(brr.begin(), brr.end());

    vector<vector<int>> hashMap(iMax+1);
    for (int i=1; i<=n; i++) hashMap[brr[i]].push_back(i);

    for (int i=1; i<=n; i++) {
        dp[i][0]=0;
        for (int j=1; j<=tot; j++) {
            dp[i][j] = dp[i-1][j];
            int aa = upper_bound(hashMap[arr[i]].begin(), hashMap[arr[i]].end(), dp[i][j-1]) - hashMap[arr[i]].begin();
            if (aa < hashMap[arr[i]].size()) dp[i][j] = min(dp[i][j], hashMap[arr[i]][aa]);
            if (j > res && j * cost + i + dp[i][j] <= total)  res=j;
        }
    }
    cout << res << endl;
}