結果
問題 | No.2759 Take Pictures, Elements? |
ユーザー |
![]() |
提出日時 | 2024-12-04 23:45:54 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 280 ms / 2,000 ms |
コード長 | 1,390 bytes |
コンパイル時間 | 1,471 ms |
コンパイル使用メモリ | 166,200 KB |
実行使用メモリ | 7,848 KB |
最終ジャッジ日時 | 2025-06-20 13:22:02 |
合計ジャッジ時間 | 2,494 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
//sakusen //dp[M][x] B_Mまで撮影し終え、しかもそのとき機会が一xにあるときの層移動コストの最小値 //B_M=A_xが必要 そうでないならてきとうに998244353(とてもおおきい)にでもしとけ #include<bits/stdc++.h> using namespace std; int main(){ int N,Q; cin >> N >> Q; vector<int> A(N+1); vector<int> B(Q+1); for(int i=1;i<=N;i++){ cin >> A[i]; } for(int i=1;i<=Q;i++){ cin >> B[i]; } vector<vector<int>> dp(Q+1, vector<int>(N+1)); for(int i=1;i<=N;i++){ if(A[i] == B[1]){ dp[1][i] = i-1; } else { dp[1][i] = 998244353; } } int min_temp = 998244353; int cost = 0; for(int m=2;m<=Q;m++){ for(int x=1;x<=N;x++){ //dp[m][x]求めるよ if(A[x] != B[m]){ dp[m][x] = 998244353; } else { min_temp = 998244353; for(int x_0=1;x_0<=N;x_0++){ cost = dp[m-1][x_0] + abs(x-x_0); if(cost < min_temp){ min_temp = cost; } } dp[m][x] = min_temp; } } } int min = 998244353; for(int x=1;x<=N;x++){ if(dp[Q][x] < min){ min = dp[Q][x]; } } cout << min << endl; }