結果

提出番号 2189
提出者 siser
言語 C++
提出日時 2018-11-27 20:14:46
問題名 (70)アルゴリズムのお勉強
結果 AC
点数 100%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 AC 100% 2ms 7872KB
2 AC 100% 2ms 8448KB
3 AC 100% 2ms 7824KB
4 AC 100% 2ms 8496KB
5 AC 100% 2ms 8224KB
6 AC 100% 2ms 8192KB
7 AC 100% 2ms 8032KB
8 AC 100% 2ms 8224KB
9 AC 100% 2ms 8416KB
10 AC 100% 1ms 8736KB
11 AC 100% 2ms 8224KB
12 AC 100% 2ms 8448KB
13 AC 100% 2ms 8224KB
14 AC 100% 2ms 8304KB
15 AC 100% 2ms 8208KB
16 AC 100% 2ms 8528KB
17 AC 100% 2ms 7600KB
18 AC 100% 2ms 8416KB
19 AC 100% 2ms 7920KB
20 AC 100% 2ms 8400KB
21 AC 100% 2ms 8016KB
22 AC 100% 2ms 7840KB
23 AC 100% 2ms 8704KB
24 AC 100% 4ms 8192KB
25 AC 100% 2ms 8656KB
26 AC 100% 3ms 8320KB
27 AC 100% 3ms 7872KB
28 AC 100% 2ms 8224KB
29 AC 100% 12ms 8224KB
30 AC 100% 3ms 8432KB

ソースコード

#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define repr(i,a,b) for(int i=(a); i>=(b); i--)
#define all(x) (x).begin(),(x),end()
typedef long long ll;
const int INF=1<<29;

int N;
int t[20];
int a[20][20];
//dp[S]:部分集合Sだけの問題を解くときにかかる最短の時間
int dp[(1<<16)+10];

int main(){
    
    cin>>N;
    rep(i,0,N)cin>>t[i];
    rep(i,0,N)rep(j,0,N)cin>>a[i][j];
    
    //bitDP
    //初期化
    rep(i,0,1<<N)dp[i]=INF;
    //dp初期条件:dp[0]=0;
    dp[0]=0;
    //dp漸化式:Sの部分集合を全列挙
    //dp[msk+{i}]=min(dp[msk+{i}],dp[msk+{i}]+t[i]-a[j][i])(j∈msk)
    rep(msk,0,1<<N) rep(i,0,N){
        if(!(msk & (1<<i))){//iが部分集合mskに含まれないときは追加処理を行える
            int k=0;
            rep(j,0,N){
                //jがmskに含まれるとき、その数だけ時間は減る(2重に縮まる可能性を考慮する)
                if(msk & (1<<j))k-=a[j][i];
            }
            dp[msk+(1<<i)]=min(dp[msk+(1<<i)],dp[msk]+t[i]+k);
        }
    }
    //求める値:dp[(1<<N)-1](全てのフラグが立っている)
    cout<<dp[(1<<N)-1]<<endl;
    
    return 0;
}