結果

提出番号 2167
提出者 birdway
言語 C++
提出日時 2018-08-22 19:46:32
問題名 (70)アルゴリズムのお勉強
結果 AC
点数 100%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 AC 100% 2ms 8464KB
2 AC 100% 2ms 7632KB
3 AC 100% 2ms 8432KB
4 AC 100% 2ms 7984KB
5 AC 100% 2ms 8080KB
6 AC 100% 2ms 8720KB
7 AC 100% 2ms 8704KB
8 AC 100% 2ms 8016KB
9 AC 100% 2ms 8064KB
10 AC 100% 2ms 8432KB
11 AC 100% 2ms 8112KB
12 AC 100% 2ms 8192KB
13 AC 100% 2ms 7776KB
14 AC 100% 2ms 8064KB
15 AC 100% 2ms 7904KB
16 AC 100% 2ms 7536KB
17 AC 100% 2ms 7984KB
18 AC 100% 2ms 8416KB
19 AC 100% 2ms 8672KB
20 AC 100% 2ms 7984KB
21 AC 100% 2ms 8064KB
22 AC 100% 3ms 8432KB
23 AC 100% 2ms 7248KB
24 AC 100% 5ms 8464KB
25 AC 100% 2ms 7920KB
26 AC 100% 3ms 7952KB
27 AC 100% 4ms 7232KB
28 AC 100% 2ms 8672KB
29 AC 100% 15ms 8064KB
30 AC 100% 3ms 8672KB

ソースコード

#include<iostream>
#include<set>
#include <bitset>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include <cstdio>
#include<algorithm>
#include <sstream>
#include<string>
#include<string.h>
#include <cmath>
#include <iomanip>
#include <string>
#include<list>
#include <limits>
#include <numeric>
#include <type_traits>
#include<bitset>
#define int long long
#define ll long long
#define mod  1000000007
#define inf 1e17
#define rep(i,j,n) for(int i=j;i<n;i++)
#define P pair<int,int>
double pi = 3.141592653589793;
using namespace std;
//ここから始めよう
int dp[1<<20];//この集合のときの最小値
int n;int a[20];
int t[20][20];
int sum(int bit,int j){
    int s=0;
    rep(i,0,n){
        if(bit&1<<i)s+=t[i][j];
    }return s;
}
int z=0;
int solve(int bit){
    int res=dp[bit];
    if(~res)return res;
    res=inf;
    if(bit==0)return 0;
    rep(i,0,n){
        if(!(bit&1<<i))continue;
        res=min(res,solve(bit & ~(1<<i))+max(z,a[i]-sum(bit & ~(1<<i),i)));
    }
    dp[bit]=res;
   // cout<<res<<" "<<bit<<endl;
    return dp[bit];
}
signed main(){
    cin>>n;
    rep(i,0,n)cin>>a[i];
    rep(i,0,n)rep(j,0,n)cin>>t[i][j];
    memset(dp,-1,1<<18);
    cout<<solve((1<<n)-1)<<endl;return 0;
}