結果
問題 | No.1818 6 Operations |
ユーザー |
![]() |
提出日時 | 2022-02-14 12:04:04 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 73 ms / 2,500 ms |
コード長 | 993 bytes |
コンパイル時間 | 3,130 ms |
コンパイル使用メモリ | 251,448 KB |
実行使用メモリ | 59,904 KB |
最終ジャッジ日時 | 2024-06-29 06:10:04 |
合計ジャッジ時間 | 4,834 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;int edit_dist(vector<int> &a,vector<int> &b){vector<vector<int>> dp(a.size()+1,vector<int>(b.size()+1));for(int i=0;i<=a.size();++i){dp[i][0]=i;}for(int i=1;i<=b.size();++i){dp[0][i]=i;}for(int i=1;i<=a.size();++i){for(int j=1;j<=b.size();++j){dp[i][j]=dp[i-1][j-1];if(a[i-1]!=b[j-1]){dp[i][j]=min(dp[i-1][j],dp[i][j]);dp[i][j]=min(dp[i][j-1],dp[i][j]);++dp[i][j];}}}return dp[a.size()][b.size()];}int main(){int input;vector<int> N(2);vector<vector<int>> A(2,vector<int>(0));cin>>N[0]>>N[1];for(int i=0;i<2;++i){for(int j=0;j<N[i];++j){cin>>input;A[i].emplace_back(0);for(int k=0;k<input;++k){A[i].emplace_back(1);}}}cout<<(edit_dist(A[0],A[1]))<<endl;}