提出番号 | 2201 |
---|---|

提出者 | hamuhei4869 |

言語 | C++ |

提出日時 | 2019-02-09 00:50:07 |

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

結果 | WA |

点数 | 0% |

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

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

2 | WA | 0% | 2ms | 8160KB |

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

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

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

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

7 | WA | 0% | 2ms | 8080KB |

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

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

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

11 | WA | 0% | 2ms | 7840KB |

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

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

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

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

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

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

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

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

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

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

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

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

24 | WA | 0% | 2ms | 7872KB |

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

26 | WA | 0% | 8ms | 8480KB |

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

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

29 | WA | 0% | 5ms | 18032KB |

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

```
#include <bits/stdc++.h>
using LL = long long;
const LL MOD = 1e9+9;
using namespace std;
vector<vector<int>> dp;
vector<int> task;
vector<vector<int>> Edge;
int N;
int calc(int bit, int now){
// cout<<bitset<10>(bit)<<endl;
if(bit == (1<<N)-1){
return 0;
}
if(dp[bit][now] != 1e9){
return dp[bit][now];
}
for(int a = 0;a < N;a++){
if(a == now)continue;
if(!((1<<a)&bit)){
int totalmi = 0;
for(int b = 0;b < N;b++){
if(bit & (1<<b)){
totalmi += Edge.at(b).at(a);
}
}
return dp[bit][now] = calc(bit | (1<<a),a) + max(0,task.at(a)-totalmi);
}
}
}
int main(){
cin >> N;
for(int a = 0;a < N;a++){
int b;cin >> b;
task.push_back(b);
}
dp = vector<vector<int>>((1<<N)+1,vector<int>(N,1e9));
for(int a = 0;a < N;a++){
vector<int> uku;
for(int b = 0;b < N;b++){
int c;cin >> c;
uku.push_back(c);
}
Edge.push_back(uku);
}
int ans = 1e9;
for(int a = 0;a < N;a++){
ans = min(ans, calc(0 | (1<<a),a)+task.at(a));
// cout<<ans<<endl;
}
cout<<ans<<endl;
}
```