結果
問題 | No.422 文字列変更 (Hard) |
ユーザー |
|
提出日時 | 2022-09-10 19:48:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 92 ms / 3,000 ms |
コード長 | 2,776 bytes |
コンパイル時間 | 2,405 ms |
コンパイル使用メモリ | 203,232 KB |
最終ジャッジ日時 | 2025-02-07 04:09:45 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 16 |
ソースコード
#include<bits/stdc++.h>using namespace std;#pragma GCC optimize("Ofast")#define rep(i,n) for(ll i=0;i<n;i++)#define repl(i,l,r) for(ll i=(l);i<(r);i++)#define per(i,n) for(ll i=(n)-1;i>=0;i--)#define perl(i,r,l) for(ll i=r-1;i>=l;i--)#define fi first#define se second#define pb push_back#define ins insert#define pqueue(x) priority_queue<x,vector<x>,greater<x>>#define all(x) (x).begin(),(x).end()#define CST(x) cout<<fixed<<setprecision(x)#define vtpl(x,y,z) vector<tuple<x,y,z>>#define rev(x) reverse(x);using ll=long long;using vl=vector<ll>;using vvl=vector<vector<ll>>;using pl=pair<ll,ll>;using vpl=vector<pl>;using vvpl=vector<vpl>;const ll MOD=1000000007;const ll MOD9=998244353;const int inf=1e9+10;const ll INF=4e18;const ll dy[9]={1,0,-1,0,1,1,-1,-1,0};const ll dx[9]={0,1,0,-1,1,-1,1,-1,0};template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}ll base=5000;ll tr(ll x,ll y,ll z){return x*base*base+y*base+z;}tuple<ll,ll,ll> rv(ll f){tuple<ll,ll,ll> p={f/base/base,(f/base)%base,f%base};return p;}int main(){ll n,m;cin >> n >> m;string s,t;cin >> s >> t;ll dp[n+1][m+1][3],ndp[n+1][m+1][3];rep(i,n+1)rep(j,m+1)rep(k,3)dp[i][j][k]=INF,ndp[i][j][k]=-1;dp[0][0][0]=0;rep(i,n+1){rep(j,m+1){if(chmin(dp[i][j][0],dp[i][j][1]))ndp[i][j][0]=tr(i,j,1);if(chmin(dp[i][j][0],dp[i][j][2]))ndp[i][j][0]=tr(i,j,2);if(chmin(dp[i][j][1],dp[i][j][0]+7))ndp[i][j][1]=tr(i,j,0);if(chmin(dp[i][j][2],dp[i][j][0]+7))ndp[i][j][2]=tr(i,j,0);if(i<n&&j<m){if(s[i]==t[j]){if(chmin(dp[i+1][j+1][0],dp[i][j][0]))ndp[i+1][j+1][0]=tr(i,j,0);}else {if(chmin(dp[i+1][j+1][0],dp[i][j][0]+5))ndp[i+1][j+1][0]=tr(i,j,0);}}if(i<n){if(chmin(dp[i+1][j][1],dp[i][j][1]+2))ndp[i+1][j][1]=tr(i,j,1);}if(j<m){if(chmin(dp[i][j+1][2],dp[i][j][2]+2))ndp[i][j+1][2]=tr(i,j,2);;}}}cout << dp[n][m][0] << endl;string rs,rt;ll x=n,y=m,z=0;while(ndp[x][y][z]!=-1){auto [nx,ny,nz]=rv(ndp[x][y][z]);if(nx!=x&&ny!=y){rs+=s[nx],rt+=t[ny];}else if(nx!=x){rs+=s[nx],rt+='-';}else if(ny!=y){rs+='-',rt+=t[ny];}x=nx,y=ny,z=nz;}rev(all(rs));rev(all(rt));cout << rs << endl;cout << rt << endl;}