提出番号 | 2182 |
---|---|

提出者 | 小林くん |

言語 | C++ |

提出日時 | 2018-10-15 23:14:39 |

問題名 | (70)アルゴリズムのお勉強 |

結果 | WA |

点数 | 0% |

テストケース | 結果 | 得点 | 実行時間 | メモリ使用量 |
---|---|---|---|---|

1 | WA | 0% | 2ms | 8384KB |

2 | WA | 0% | 2ms | 8320KB |

3 | WA | 0% | 2ms | 8448KB |

4 | WA | 0% | 2ms | 8208KB |

5 | WA | 0% | 2ms | 8320KB |

6 | WA | 0% | 2ms | 7888KB |

7 | WA | 0% | 1ms | 7792KB |

8 | WA | 0% | 2ms | 8416KB |

9 | WA | 0% | 2ms | 7600KB |

10 | WA | 0% | 2ms | 8064KB |

11 | WA | 0% | 1ms | 8496KB |

12 | WA | 0% | 2ms | 7488KB |

13 | WA | 0% | 2ms | 7888KB |

14 | WA | 0% | 2ms | 8608KB |

15 | WA | 0% | 2ms | 8208KB |

16 | WA | 0% | 2ms | 8448KB |

17 | WA | 0% | 2ms | 7600KB |

18 | WA | 0% | 2ms | 7232KB |

19 | WA | 0% | 2ms | 8048KB |

20 | WA | 0% | 2ms | 8512KB |

21 | WA | 0% | 1ms | 8688KB |

22 | WA | 0% | 2ms | 7904KB |

23 | WA | 0% | 2ms | 8432KB |

24 | WA | 0% | 1ms | 7888KB |

25 | WA | 0% | 2ms | 8288KB |

26 | WA | 0% | 2ms | 8224KB |

27 | WA | 0% | 2ms | 7536KB |

28 | WA | 0% | 2ms | 7600KB |

29 | WA | 0% | 2ms | 8432KB |

30 | WA | 0% | 2ms | 7504KB |

```
#include <stdio.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]);
}
}
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
dp[i][j]=-1;
}
}
printf("%d",cal(0, 0));
return 0;
}
```