记录编号	203638	评测结果	AAAAAAAAAA
题目名称	[USACO Jan09] 气象牛	最终得分	100
用户昵称	霓虹灯下的码农	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2015-11-03 13:45:35	内存使用	0.39 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdlib>
#include<queue>
#include<vector>
using namespace std;
int dp[110][110];
int jilu[110][110];
int end[110];
int n,E;
int m[110];
bool judge(int k)
{
     int ans=1<<30;
     for (int i=k;i<=n;i++)
         if (dp[i][k]+end[i]<ans) ans=dp[i][k]+end[i];
     if (ans<=E)
     {
        printf("%d %d",k,ans);
        return true;
     }
     else return false;
}
int mid(int l,int r)
{
    if (jilu[l][r]!=0) return jilu[l][r];
    int ans=0;
    for (int i=l+1;i!=r;i++) 
    ans+=abs(2*m[i]-m[l]-m[r]);
    return ans;
}
int main()
{
    freopen("baric.in","r",stdin);
    freopen("baric.out","w",stdout);
    scanf("%d %d",&n,&E);
    for (int i=1;i<=n;i++) scanf("%d",&m[i]);
    dp[1][1]=0;
    for (int i=2;i<=n;i++)
        for (int j=1;j<i;j++)  dp[i][1]+=2*abs(m[i]-m[j]);
    end[n+1]=0;
    end[n]=0;
    for (int i=n-1;i>=1;i--)
        for (int j=i+1;j<=n;j++) end[i]+=2*abs(m[i]-m[j]);
    int i,j=1,k;
    while (1)
    {
         if (judge(j)) break;
         j++;
         for (i=j;i<=n;i++)
         {
             dp[i][j]=1<<30;
             for (k=j-1;k<i;k++)
             {
                 jilu[k][i]=mid(k,i);
                 if (dp[k][j-1]+jilu[k][i]<dp[i][j])
                 dp[i][j]=dp[k][j-1]+jilu[k][i];
             }
         }
    }
    fclose(stdin);
    fclose(stdout);
    
    return 0;
}