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) 回帖