BARIC - Bò Ba-ri
Tác giả: ll931110
Ngôn ngữ: C++
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;
int n,E;
int cost[102][102],f[102][102];
int a[102];
int main()
{
// freopen("baric.in","r",stdin);
// freopen("baric.ou","w",stdout);
scanf("%d %d", &n, &E);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++)
{
cost[0][i] = 0;
for (int j = 1; j < i; j++) cost[0][i] += 2 * abs(a[j] - a[i]);
};
for (int i = 1; i <= n; i++)
{
cost[i][n + 1] = 0;
for (int j = i + 1; j <= n; j++) cost[i][n + 1] += 2 * abs(a[j] - a[i]);
};
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
{
cost[i][j] = 0;
for (int k = i + 1; k < j; k++) cost[i][j] += abs(2 * a[k] - a[i] - a[j]);
};
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) f[i][j] = 1000000000;
for (int i = 1; i <= n; i++) f[i][1] = cost[0][i];
int ret = 1,opt = 1000000000;
while (1)
{
opt = 1000000000;
for (int i = 1; i <= n; i++) opt = min(opt,f[i][ret] + cost[i][n + 1]);
if (opt <= E) break;
ret++;
for (int i = 1; i <= n; i++)
for (int j = 1; j < i; j++) f[i][ret] = min(f[i][ret],f[j][ret - 1] + cost[j][i]);
};
printf("%d %d\n", ret, opt);
};