BARIC - Bò Ba-ri
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <iostream>
using namespace std;
int E, n, rr;
int w[111];
int F[111][111], C[111][111];
bool check(int K) {
memset( F, 0x1f, sizeof(F));
F[1][0] = 0;
for(int t=2;t<=K;++t)
for(int i=1;i<2+n;++i)
for(int last=0;last<i;++last)
F[t][i] <?= F[t-1][last] + C[last][i];
rr = F[K][n+1];
return rr <= E;
}
int main() {
scanf("%d%d", &n, &E);
for(int i=1;i<=n;++i)
scanf("%d", &w[i]);
w[0] = w[n+1] = 0;
for(int i=0;i<n+2;++i)
for(int j=i+1;j<n+2;++j)
for(int k=i+1;k<j;++k)
if(i==0) C[i][j] += 2 * abs(w[k]-w[j]);
else if(j==n+1) C[i][j] += 2 * abs(w[k] - w[i]);
else C[i][j] += abs( 2 * w[k] - w[i] - w[j]);
int r = n + 2;
for(int i=1<<8;i>0;i>>=1)
if(r-i>=3 && check(r-i)) r -= i;
check(r);
cout << r - 2 << " " << rr << endl;
//system("pause");
return 0;
}