একটি পজিটিভ ইন্টিজার অ্যারে দেওয়া আছে। প্রতিটি উপাদান পরিবর্তন করতে হবে যেন আডজেসেন্ট উপাদান দুটির পার্থক্য ≤ target হয়। পরিবর্তনের খরচ = Σ|A[i] - A_new[i]|। এই খরচ ন্যূনতম করতে হবে। সব উপাদান < 100 (M=100)।
উদাহরণ
arr = [56,78,53,62,40,7,26,61,50,48], target = 20
আউটপুট: Minimum adjustment cost is 35
DP রিলেশন
dp[i][j] = i-তম উপাদানকে j-এ পরিবর্তন করলে ন্যূনতম কস্ট
dp[i][j] = min_{k: |k-j|≤target} ( dp[i-1][k] ) + |j - A[i]|
বেস: dp[0][j] = |j - A[0]|। উত্তর: min_j dp[n-1][j]।
C++ প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
#define M 100
int minAdjustmentCost(int A[], int n, int target) {
int dp[n][M+1];
for (int j=0;j<=M;j++) dp[0][j] = abs(j - A[0]);
for (int i=1;i
আউটপুট: Minimum adjustment cost is 35
