BARIC - Bò Ba-ri
Tác giả: hieult
Ngôn ngữ: C++
#include <stdio.h>
//#include <conio.h>
#define max 1000000000
int TTD(int n)
{
if(n<0) return -n;
else return n;
}
int main()
{
// freopen("BARIC.in","r",stdin);
int n,E,a[101],f[101][101],d[101][101],KQ = 0,flag=0;
scanf("%d %d",&n,&E);
for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
int tt = max;
for(int i = 1;i<=n;i++)
{
f[1][i]=0;
for(int j = 1;j<=n;j++)
f[1][i] = f[1][i]+2*TTD(a[j]-a[i]);
if(f[1][i]<=E)
{
if(f[1][i]<tt) tt = f[1][i];
KQ = 1; }
//printf("%d ",f[1][i]);
}
if(KQ!=0)
printf("%d %d",KQ,tt);
else
{
for(int i = 1;i<=n-1;i++)
for(int j = i+1;j<=n;j++)
{
d[i][j] = 0;
for(int k = j;k<=n;k++)
d[i][j] = d[i][j]+2*TTD(a[k]-a[j])-2*TTD(a[k]-a[i]);
for(int k = i+1;k<j;k++)
d[i][j] = d[i][j]+TTD(2*a[k]-a[i]-a[j])-2*TTD(a[k]-a[i]);
// printf("%d %d %d\n",i,j,d[i][j]);
}
for(int i = 2;i<=n;i++)
{
tt=max;
for(int j = 1;j<=n;j++)
{
if(j<i)
{
f[i][j] = max;
//continue;
}
else
{
f[i][j] = max;
for(int k = j-1;k>=i-1;k--)
{
if(f[i-1][k]+d[k][j]<f[i][j])
f[i][j] = f[i-1][k]+d[k][j];
}
}
if(f[i][j]<=E)
{
if(f[i][j]<tt)
tt =f[i][j];
KQ = i;}
// printf("%d %d %d\n",i,j,f[i][j]);
}
if(KQ!=0)
{
printf("%d %d",KQ,tt);
break;
}
}
}
// getch();
}