首页 > 网易9.12 C++开发,最后两个大题,7的倍数和编辑距离
头像
没是拉速度快你发的
编辑于 2020-09-12 18:14
+ 关注

网易9.12 C++开发,最后两个大题,7的倍数和编辑距离

7的倍数:
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int N = 100010;
int V[N];
int f[N][7];

int main()
{
    int n = 0;
    while(cin>>V[n++],V[n-1]);
    memset(f,-1,sizeof f);
    f[0][0] = 0;
    for(int i = 0;i < n;i ++){
        for(int j = 0;j < 7;j ++){
            f[i+1][j] = max(f[i+1][j],f[i][j]) ;
            if(f[i][j] == -1) continue;
            int t = (j + V[i])%7;
            f[i+1][t] = max(f[i+1][t],f[i][j]+V[i]);
        }
    }
    cout<<f[n][0];
    return 0;
}
编辑距离:
#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

unordered_set<string> set;

vector<string> getarr(string& S){
    int idx = 0;
    vector<string> res;
    while(idx < S.size()){
        string arr;
        while(idx < S.size()&&S[idx] != ' '){
            arr += S[idx];
            idx++;
        }
        idx++;
        if(arr.size()) res.push_back(arr);
    }
    return res;
}

void dp(vector<string>& A,vector<string>& B){
    int n = A.size(),m = B.size();
    vector<vector<int>> f(n+1,vector<int>(m+1,1e9));
    f[0][0] = 0;
    for(int i = 1;i <= n;i ++)
        if(set.count(A[i-1])) f[i][0] = f[i-1][0];
        else f[i][0] = f[i-1][0]+1;
        
    for(int i = 1;i <= m;i ++)
        if(set.count(B[i-1])) f[0][i] = f[0][i-1];
        else f[0][i] = f[0][i-1]+1;
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            if(set.count(A[i-1])){
                f[i][j] = min(f[i][j],f[i-1][j]);
            }
            if(set.count(B[j-1])){
                f[i][j] = min(f[i][j],f[i][j-1]);
            }
            if(set.count(A[i-1])&&set.count(B[j-1])){
                f[i][j] = min(f[i][j],f[i-1][j-1]);
            }
            if(A[i-1] == B[j-1]){
                f[i][j] = min(f[i-1][j-1],f[i][j]);
                f[i][j] = min(f[i-1][j]+1,f[i][j]);
                f[i][j] = min(f[i][j-1]+1,f[i][j]);
            }
            else{
                f[i][j] = min(f[i-1][j-1]+1,f[i][j]);
                f[i][j] = min(f[i-1][j]+1,f[i][j]);
                f[i][j] = min(f[i][j-1]+1,f[i][j]);
            }
        }
    }
    cout<<f[n][m];
}

int main()
{

    string temp1;
    getline(cin,temp1);
    int idx = 0;
    while(idx < temp1.size()){
        string arr;
        while(idx < temp1.size()&&temp1[idx] != ' '){
            arr += temp1[idx];
            idx++;
        }
        idx++;
        set.insert(arr);
    }
    string A,B;
    getline(cin,A),getline(cin,B);
    auto VA = getarr(A);
    auto VB = getarr(B);

    dp(VA,VB);
    return 0;
}


全部评论

(0) 回帖
加载中...
话题 回帖