結果
問題 | No.771 しおり |
ユーザー |
![]() |
提出日時 | 2024-06-30 12:57:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 192 ms / 2,000 ms |
コード長 | 1,096 bytes |
コンパイル時間 | 2,063 ms |
コンパイル使用メモリ | 194,904 KB |
最終ジャッジ日時 | 2025-02-22 01:37:33 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
#include<bits/stdc++.h>using namespace std;const long inf = 1e9;int A[21],B[21];int dist[20][20];int dp[(1 << 20)][20];int main(void){long long n;cin >> n;for(int i=0;i<n;i++){cin >> A[i] >> B[i];}for(int i=0;i<n;i++){for(int j=0;j<n;j++){dist[i][j]=abs(B[i]-A[i])+abs(A[j]);}}for(int i=0;i<(1<<20);i++){for(int j=0;j<n;j++){dp[i][j]=inf;}}for(int i=0; i<n; i++) dp[1<<i][i] = 0;//1冊目はゼロ// 1は選択済み。0はこれからfor(int msk=0; msk<(1<<n); msk++){for(int i=0;i<n;i++){//nowfor(int j=0; j<n; j++){//nextif((msk & (1<<i))){//nowif(!(msk & (1<<j))){//nextint cost = dist[i][j];dp[msk+(1<<j)][j]= min(dp[msk+(1<<j)][j],max(dp[msk][i],cost));//多い条件を残す}}}}}int ans=inf;for(int i=0;i<n;i++){ans=min(ans,dp[(1<<n)-1][i]);}cout << ans << endl;return 0;}