結果

提出番号 2183
提出者 小林くん
言語 C++
提出日時 2018-10-15 23:22:38
問題名 (70)アルゴリズムのお勉強
結果 WA
点数 0%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 WA 0% 4ms 21248KB
2 AC 100% 4ms 21248KB
3 WA 0% 4ms 21232KB
4 AC 100% 4ms 21232KB
5 WA 0% 4ms 21248KB
6 WA 0% 4ms 21232KB
7 WA 0% 4ms 21232KB
8 WA 0% 4ms 21232KB
9 WA 0% 3ms 21232KB
10 WA 0% 4ms 21248KB
11 WA 0% 5ms 21248KB
12 WA 0% 4ms 21248KB
13 WA 0% 5ms 21248KB
14 WA 0% 4ms 21248KB
15 WA 0% 4ms 21232KB
16 AC 100% 4ms 21232KB
17 WA 0% 4ms 21232KB
18 WA 0% 4ms 21248KB
19 AC 100% 7ms 21232KB
20 WA 0% 6ms 21232KB
21 WA 0% 4ms 21232KB
22 WA 0% 10ms 21248KB
23 WA 0% 4ms 21248KB
24 WA 0% 17ms 21232KB
25 AC 100% 6ms 21248KB
26 WA 0% 9ms 21232KB
27 WA 0% 17ms 21232KB
28 WA 0% 6ms 21248KB
29 WA 0% 79ms 21232KB
30 WA 0% 10ms 21248KB

ソースコード

#include <iostream>
#include <stdlib.h>
#include <string.h>

#define max_n 16
int N;
int cost[max_n];
int easy[max_n][max_n];
int dp[1<<max_n][max_n];

int cal(int a,int b){
    
    if (dp[a][b]>=0) {
        return dp[a][b];
    }
    
    if (a==(1<<N)-1&&b==0) {
        return dp[a][b]=0;
    }
    //aは通った道,bは今いる位置
    
    int res=2000000;
    
    for (int i=0; i<N; i++) {
        if (!(a>>i&1)) {
            int d=cost[i];
            
            for (int j=0; j<N; j++) {
                if (a>>j&1) {
                    d-=easy[j][i];
                }
            }
            
            if (res>cal(a|1<<i, i)+d) {
                res=cal(a|1<<i, i)+d;
            }
        }
    }
    
    return dp[a][b]=res;
}

int main() {
    
    scanf("%d",&N);
    
    for (int i=0; i<N; i++) {
        scanf("%d",&cost[i]);
    }
   
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            scanf("%d",&easy[i][j]);
        }
    }
    
    memset(dp, -1, sizeof(dp));
    
    printf("%d",cal(0, 0));
    
}