Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- int main()
- {
- /// problem: https://lightoj.com/problem/coin-change-iii
- dpp[n+1][0] = 1;
- for(int rem = 1 ; rem <= m ; rem++) dpp[n+1][rem] = 0;
- for(int cur = n ; cur > 0 ; cur--){
- for(int i = 0 ; i < A[cur] ; i++) vec[i].clear();
- // for(int rem = 0 ; rem <= m ; rem){
- // vec[rem % mod].push_back(dpp[cur+1][rem]);
- // }
- for(int mod = 0 ; mod < A[cur] ; mod++){
- for(int rem = mod ; rem <= m ; rem += A[cur]){
- if(vec[mod].size() > 0){
- vec[mod].push_back(vec[mod].back() + dpp[cur+1][rem]);
- }
- else vec[mod].push_back(dpp[cur+1][rem]); /// index = 0
- }
- }
- for(int mod = 0 ; mod < A[cur] ; mod++){
- for(int rem = mod , index = 0; rem <= m ; rem += A[cur] , index = index + 1){
- int sum = PrefixSum(vec[mod] , index , index - C[cur]);
- if(sum > 0) dpp[cur][rem] = 1;
- else dpp[cur][rem] = 0;
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement