题解 P2933 【[USACO09JAN]气象测量The Baric Bovine】

· · 题解

题目大意:

给你一个集合，告诉你如何判定它的子集是否合法并让你找到一个最优子集

解法：

首先我们预处理出一个数组ero，ero[i][j]保存在i到j之间元素对误差的贡献，即我们枚举k(j-1>=k>=i+1)，计算abs(2*m[z]-m[i]-m[j])

特殊的是，我们还需要处理出ero[i][0]和ero[i][n+1]，分别表示在i之间和在i之后的元素的各种误差

考虑如何DP

定义DP[i][j]表示前j个元素，必选第j个元素，总共选择了i个产生的最小误差。为什么把i放在前，j放在后呢？

因为我们首先最小化的是子集的大小。

状态转移方程就是：

dp[i][j]=min(dp[i][j],dp[i-1][q]+sum)(i-1<=q<=j)

我们有sum=-pre[q][n+1]+pre[q][j]+pre[j][n+1]（之前我们是把q当成是子集的结尾并加上了它之后对误差的贡献，于是此时我们减去这个值改为用j来作为最后一个元素）

注意

i=1的情况必须我们提前处理出来才可以

code:

#include<bits/stdc++.h>
using namespace std;
int n,e;
long long m[110],ero[110][110],dp[110][110];
//ero选i和j产生的误差
//dp以j结尾的时候，有i个最少测量数目 能达到的最小误差 
long long abss(long long a)
{
    if(a<0)return -a;
    return a;
}
int main()
{
    int i,j,k;
    scanf("%d%d",&n,&e);
    for(i=1;i<=n;i++)scanf("%lld",&m[i]);    
    long long ans=n,anss=999999999;
    for(k=1;k<=n;k++)//计算误差 
    {
        for(i=k+1;i<=n;i++)
            for(j=k+1;j<=i-1;j++) /*枚举题中的i*/ 
                ero[k][i]+=abss(2*m[j]-m[i]-m[k]);//误差 计算---情况一 

        for(i=1;i<k;i++) ero[k][0]+=2*abss(m[i]-m[k]); //误差 计算---情况二 
        for(i=k+1;i<=n;i++) ero[k][n+1]+=2*abss(m[i]-m[k]);// 误差 计算---情况三 
    }
    for(i=1;i<=n;i++) //处理只取一个数的情况，也就是只取数i的情况 预处理 
    {
        dp[1][i]=ero[i][0]+ero[i][n+1]; 
        if((dp[1][i]<=e) && (dp[1][i]<anss))
        {
            anss=dp[1][i];ans=1;
        }
    }

    if(ans==1){printf("%lld %lld\n",ans,anss);return 0;}

    for(k=2;k<=n;k++)//最少能达到误差小于等于E的测量数目
        for(i=k;i<=n;i++)//枚举结尾的数 
        {
            dp[k][i]=0x7fffffff;
            for(j=k-1;j<i;j++)//枚举上一轮的结尾数 
            {
                long long err=ero[j][i]+ero[i][n+1]-ero[j][n+1]; //相比上一轮多的误差 
                dp[k][i]=min(dp[k][i],dp[k-1][j]+err);
            }
            if((dp[k][i]<=e)&&(dp[k][i]<anss)&&(k<=ans))
                anss=dp[k][i],ans=k; 
        }
    printf("%lld %lld",ans,anss);
    return 0;
}