| 25 | */ |
| 26 | |
| 27 | int solve(int idx, int pos) { |
| 28 | // base case, return 0 |
| 29 | if(idx == n) return 0; |
| 30 | int ans = inf; |
| 31 | |
| 32 | if(dp[idx][pos]!=-1) return dp[idx][pos]; |
| 33 | |
| 34 | // for every available posistion we place the current number in it and we |
| 35 | // transition to the next state |
| 36 | for(int i=pos;i<=2*n;i++) { |
| 37 | // cost |
| 38 | int c = abs(arr[idx]-(i+1)); |
| 39 | // add the cost and update the next free position, as the array is |
| 40 | // sorted, we only need to check positions starting from the next smaller not |
| 41 | // taken. |
| 42 | int a = c + solve(idx+1, i+1); |
| 43 | |
| 44 | ans = min(a,ans); |
| 45 | // if the cost is zero, it is optimal, so we don't need to test any |
| 46 | // further. |
| 47 | if(c == 0) break; |
| 48 | } |
| 49 | |
| 50 | return dp[idx][pos] = ans; |
| 51 | } |
| 52 | |
| 53 | int main() { |
| 54 | int q; scanf("%d",&q); |