結果

提出番号	2439
提出者	momoyuu
言語	C++
提出日時	2023-03-24 02:58:28
問題名	(70)アルゴリズムのお勉強
結果	AC
点数	100%

---

テストケース

ソースコード

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

int main(){
    int n;
    cin>>n;
    vector<int> t(n);
    for(int i = 0;i<n;i++) cin>>t[i];
    vector<vector<int> >a(n,vector<int>(n,0));
    for(int i = 0;i<n;i++)for(int j = 0;j<n;j++) cin>>a[i][j];
    vector<int>dp(1<<n,1e9);
    dp[0] = 0;
    for(int i = 0;i<1<<n;i++){
        for(int j = 0;j<n;j++){
            if(i>>j&1) continue;
            int need = t[j];
            for(int k = 0;k<n;k++)if(i>>k&1) need -= a[k][j];
            dp[i|1<<j] = min(dp[i|1<<j],dp[i]+need);
        }
    }
    cout<<dp[(1<<n)-1]<<endl;
}