提出番号 | 2221 |
---|---|

提出者 | ndifix |

言語 | C++ |

提出日時 | 2019-03-18 15:56:49 |

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

結果 | AC |

点数 | 100% |

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

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

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

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

4 | AC | 100% | 2ms | 8112KB |

5 | AC | 100% | 2ms | 7840KB |

6 | AC | 100% | 2ms | 8304KB |

7 | AC | 100% | 2ms | 7840KB |

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

9 | AC | 100% | 2ms | 8048KB |

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

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

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

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

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

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

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

17 | AC | 100% | 2ms | 7888KB |

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

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

20 | AC | 100% | 2ms | 8816KB |

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

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

23 | AC | 100% | 2ms | 7888KB |

24 | AC | 100% | 4ms | 7872KB |

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

26 | AC | 100% | 3ms | 8160KB |

27 | AC | 100% | 4ms | 8288KB |

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

29 | AC | 100% | 10ms | 8512KB |

30 | AC | 100% | 3ms | 7888KB |

```
#include <bits/stdc++.h>
#define inf 1000000000 //1E+9
#define mod 1000000007
using namespace std;
int n, t[16], a[16][16];
int dp[1<<16];
int func(int I){
if(dp[I]!=inf) return dp[I];
int buf;
for(int i=0;i<n;i++){
buf=0;
if(I & (1<<i)){
for(int j=0;j<n;j++)if(I&(1<<j)) buf+=a[j][i];
dp[I]=min(dp[I], func(I& ~(1<<i))+t[i]-buf);
}
}
return dp[I];
}
int main(){
cin>>n;
for(int i=0;i<n;i++)cin>>t[i];
for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>a[i][j];
for(int i=1;i<(1<<16);i++)dp[i]=inf;
dp[0]=0;
for(int i=0;i<n;i++)dp[int(pow(2.0,i))]=t[i];
cout<<func((1<<n)-1)<<endl;
return 0;
}
```