Untitled
unknown
c_cpp
3 years ago
6.6 kB
5
Indexable
#include <bits/stdc++.h>
#include <cstdint>
using namespace std;
using namespace std::chrono;
// datatypes
#define int long long
#define ld long double
#define ull unsigned long long
#define mii map<int, int>
#define pi pair<int, int>
#define pq priority_queue<int>
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fi first
#define se second
#define endl "\n"
#define as " "
// important constants
#define MOD 1000000007
#define INF 1LL << 57LL
#define MAX 1000000
#define pie 3.14159265358979
#define ESP (1e-9)
// Modulus-Mathematics
template <typename T, typename U>
int modMul(T a, U b) { return ((a % MOD) * 1LL * (b % MOD)) % MOD; }
template <typename T, typename U>
int binpower(T n, U k)
{
T res = 1;
while (k)
{
if (k & 1)
{
res = modMul(res, n);
}
n = modMul(n, n);
k >>= 1;
}
return res % MOD;
}
template <typename T>
T moduloInverse(T a) { return binpower(a, MOD - 2); }
template <typename T, typename U>
int modAdd(T a, U b) { return ((a % MOD) + (b % MOD)) % MOD; }
template <typename T, typename U>
int modSub(T a, U b) { return ((a % MOD) - (b % MOD) + MOD) % MOD; }
template <typename T, typename U>
int modDiv(T a, U b) { return modMul(a, moduloInverse(b)); }
// GCD and LCM
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
int lcm(int a, int b)
{
return (a / gcd(a, b)) * b;
}
// vectors
typedef vector<int> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef pair<int, bool> pib;
typedef pair<string, int> psi;
typedef pair<string, string> pss;
typedef vector<pii> vpii;
typedef vector<psi> vpsi;
typedef vector<pss> vpss;
// looping
#define fr(i, a) for (int i = 0; i < a; i++)
#define fe(i, a) for (int i = 0; i <= a; i++)
#define fu(i, a, n) for (int i = a; i < n; i++)
#define fue(i, a, n) for (int i = a; i <= n; i++)
#define fd(i, n, a) for (int i = n; i > a; i--)
#define fde(i, n, a) for (int i = n; i >= a; i--)
#define sum(a) (accumulate((a).begin(), (a).end(), 0ll))
#define mine(a) (*min_element((a).begin(), (a).end()))
#define maxe(a) (*max_element((a).begin(), (a).end()))
#define mini(a) (min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a) (max_element((a).begin(), (a).end()) - (a).begin())
#define maxij(a, i, j) (max_element((a).begin() + i, (a).begin() + j + 1) - (a).begin())
#define lowb(a, x) (lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) (upper_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define sz(a) (int)((a).size())
#define rs(a, n) ((a).resize(n))
#define ms(a, val) ( memset((a), val, sz(a))
// debugging
#ifndef ONLINE_JUDGE
#define dg(x) \
cerr << #x << "\t"; \
_print(x); \
cerr << endl;
#define dg2(x, y) \
cerr << #x << "\t"; \
_print(x); \
cerr << "\t|\t" << #y << "\t"; \
_print(y); \
cerr << endl;
#define dg3(x, y, z) \
cerr << #x << "\t"; \
_print(x); \
cerr << "\t|\t" << #y << "\t"; \
_print(y); \
cerr << "\t|\t" << #z << "\t"; \
_print(z); \
cerr << endl;
#define dg4(x, y, z, w) \
cerr << #x << "\t"; \
_print(x); \
cerr << "\t|\t" << #y << "\t"; \
_print(y); \
cerr << "\t|\t" << #z << "\t"; \
_print(z); \
cerr << "\t|\t" << #w << "\t"; \
_print(w); \
cerr << endl;
#else
#define dg(x)
#define dg2(x, y)
#define dg3(x, y, z)
#define dg4(x, y, z, w)
#endif
void _print(int x)
{
cerr << x;
}
void _print(float x) { cerr << x; }
void _print(double x) { cerr << x; }
void _print(string x) { cerr << x; }
void _print(ull x) { cerr << x; }
void _print(char x) { cerr << x; }
void _print(bool x) { cerr << x; }
template <typename T>
vector<T> inp(int n)
{
vector<T> ain(n);
fr(i, n) cin >> ain[i];
return ain;
}
template <typename T>
void print(vector<T> arr)
{
fr(i, arr.size()) cout << arr[i] << " ";
cout << endl;
return;
}
bool isPalindrome(int x)
{
string s = to_string(x);
string t = s;
reverse(all(t));
if (s == t)
return true;
return false;
}
int n, d, ans;
vll arr;
int dp[410][410][11];
int diff(int a, int b)
{
int val = abs(a - b);
val = min(abs(min(a, b) + d - max(a, b)), val);
return val;
}
int rec(int i, int j, int k)
{
if (i < 0 || j < 0 || i > j)
{
return 0;
}
else if (i == j)
{
dp[i][j][k] = diff(arr[i], k);
}
else if (dp[i][j][k] != 1e15)
{
// return dp[i][j][k];
}
else if (arr[i] == arr[j])
{
dp[i][j][k] = rec(i + 1, j - 1, arr[i]);
dp[i][j][k] += diff(arr[i], k);
}
else
{
int a = rec(i + 1, j, arr[i]);
if (i < n - 1)
{
a += diff(k, arr[i]);
}
int b = rec(i, j - 1, arr[j]);
if (j > 0)
{
b += diff(k, arr[j]);
}
dp[i][j][k] = min(a, b);
}
// cerr << i << " " << j << " " << k << " " << dp[i][j][k] << endl;
return dp[i][j][k];
}
void solve(int t)
{
cin >> n >> d;
// cerr << n << " " << d << endl;
arr = inp<int>(n);
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= n; j++)
{
for (int k = 0; k <= 10; k++)
dp[i][j][k] = 1e15;
}
}
ans = rec(0, n - 1, 0);
// + max(0LL, min(arr[0], arr[n - 1]) - 1);
cout << "Case #" << setprecision(10) << t << ": " << ans << endl;
return;
}
int32_t main()
{
// auto start = high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// Start of Code..
int t;
cin >> t;
int p = 1;
while (t--)
{
solve(p);
p++;
}
// End of Code
// auto stop = high_resolution_clock::now(); // stop clock
// auto duration = duration_cast<microseconds>(stop - start); // printing duration
// cerr << "Time taken by function: " << duration.count() / 1000.0 << " millisec" << endl;
return 0;
}
// ___ __ __ __ ___ ___ __ __ __
// |__ |\ | / ` |__) \ / |__) | |__ | \ | |__) / _`
// |___ | \| \__, | \ | | | |___ |__/ ___ \__/ | \__>
//
Editor is loading...