[usaco jan 09] 气象牛 baric [dp]

题面：

传送门

思路：

题意有点绕，实际上就是给你一个计算规则，让你取最少的元素，通过这个计算方式，得到一个小于指定误差上限的结果

这个规则分为三个部分，这里分别用pre,sum,suf表示

因为给定的元素个数（天数）很少，可以使用O(n^3)算法，因此考虑使用经过了预处理的dp解决问题

具体地，设dp[i][j]表示前i个元素使用了j个且一定取用了第i个时可能达到的最小误差值

预处理：pre[i]表示通过第一种计算方式得到的，第一个元素取第i个时得到的误差

suf[i]同理，为第三种计算方式

sum[i][j]则表示取了i和j且不取中间的元素时，中间的元素产生的误差

这样dp[i][1]=pre[i],dp[i][j]=dp[k][j-1]+sum[k][i](k=1...i-1)，然后用dp[i][j]+suf[j]更新答案即可

Code：

 #include<iostream>

 #include<vector>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #define inf 0x7fffffff/2

 using namespace std;

 int n,m,a[];

 int dp[][];

 //dp[i][j]: prefix 1-i,chosen j

 int pre[],suf[],sum[][];

 int abs(int k){

     if(k>=) return k;

     else return -k;

 }

 int main(){

     freopen("baric.in","r",stdin);

     freopen("baric.out","w",stdout);

     int i,j,k,tmp1,tmp2,t,l;

     scanf("%d%d",&n,&m);

     int ans=m,anss=n;

     for(i=;i<=n;i++){

         scanf("%d",&a[i]);

         dp[i][]=;

     }

     for(i=;i<=n-;i++){

         for(j=i+;j<=n;j++){

             for(k=i+;k<j;k++){

                 sum[i][j]+=abs((a[k]<<)-a[i]-a[j]);

             }

         }

     }

     for(i=;i<=n;i++){

         for(j=;j<i;j++) pre[i]+=abs(a[i]-a[j])<<;

         dp[i][]=pre[i];

         for(j=n;j>i;j--) suf[i]+=abs(a[i]-a[j])<<;

     }

     for(i=;i<=n;i++){

         for(j=;j<=i;j++){

             dp[i][j]=inf/;

             for(k=;k<i;k++) dp[i][j]=min(dp[i][j],dp[k][j-]+sum[k][i]);

             if(dp[i][j]+suf[i]<m){

                 if(j<ans) ans=j,anss=dp[i][j]+suf[i];

                 else if(j==ans&&dp[i][j]+suf[i]<anss) anss=dp[i][j]+suf[i];

             }

         }

     }

     printf("%d %d",ans,anss);

 }

巴特西

[usaco jan 09] 气象牛 baric [dp]

最新文章

热门文章