提出番号 | 2213 |
---|---|

提出者 | Sometimes731 |

言語 | C++ |

提出日時 | 2019-03-12 17:29:55 |

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

結果 | AC |

点数 | 100% |

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

1 | AC | 100% | 1ms | 8240KB |

2 | AC | 100% | 1ms | 8400KB |

3 | AC | 100% | 2ms | 8064KB |

4 | AC | 100% | 1ms | 8336KB |

5 | AC | 100% | 1ms | 8176KB |

6 | AC | 100% | 1ms | 8208KB |

7 | AC | 100% | 1ms | 8752KB |

8 | AC | 100% | 2ms | 8384KB |

9 | AC | 100% | 1ms | 8160KB |

10 | AC | 100% | 2ms | 8128KB |

11 | AC | 100% | 2ms | 8160KB |

12 | AC | 100% | 2ms | 8432KB |

13 | AC | 100% | 2ms | 8752KB |

14 | AC | 100% | 2ms | 8160KB |

15 | AC | 100% | 2ms | 8144KB |

16 | AC | 100% | 2ms | 8096KB |

17 | AC | 100% | 1ms | 8464KB |

18 | AC | 100% | 2ms | 8144KB |

19 | AC | 100% | 2ms | 8448KB |

20 | AC | 100% | 3ms | 8544KB |

21 | AC | 100% | 2ms | 8160KB |

22 | AC | 100% | 3ms | 8384KB |

23 | AC | 100% | 1ms | 8288KB |

24 | AC | 100% | 6ms | 8736KB |

25 | AC | 100% | 2ms | 8768KB |

26 | AC | 100% | 4ms | 8784KB |

27 | AC | 100% | 6ms | 8160KB |

28 | AC | 100% | 2ms | 8224KB |

29 | AC | 100% | 20ms | 8112KB |

30 | AC | 100% | 4ms | 8160KB |

```
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define llINF ((long long)1e18)
#define iINF ((int)1e9)
#define ALL(obj) obj.begin(), obj.end()
using namespace std;
const int MOD = 1e9 + 7;
int N;
int dp[1 << 16], a[16][16], t[16];
int rec(int S) {
if (dp[S] != 0) {
return dp[S];
}
if (S == (1 << N) - 1) {
return 0;
}
int res = iINF;
REP(i, N) {
int tmp = t[i];
if ((S >> i) & 1) continue;
REP(j, N) {
if ((S >> j) & 1) {
tmp -= a[j][i];
}
res = min(res, rec(S | 1 << i) + tmp);
}
}
return dp[S] = res;
}
int main() {
cin >> N;
REP(i, N) { cin >> t[i]; }
REP(i, N) {
REP(j, N) { cin >> a[i][j]; }
}
cout << rec(0) << endl;
}
```