气象牛【DP】

题目大意：
有N$N$次气压测量结果，M[1]$M[1]$，M[2]...M[N]$M[2]...M[N]$。要找出一部分测量结果来总结全部的气压分布。 用K$K$个数s[1]$s[1]$，s[2]...s[N]$s[2]...s[N]$来概括所有测量结果。对于任何测量结果子集，每一个非此子集中的结果都会产生误差。总误差是所有测量结果的误差之和。误差计算如下：
　　

• 如果 i$i$小于 s[1]$s[1]$， 误差是2×|M[i]−M[s[1]]|$2\times |M[i]-M[s[1]]|$
• 如果i$i$在s[j]$s[j]$和s[j+1]$s[j+1]$之间,误差是|2×M[i]−Sum(s[j],s[j+1])|$|2\times M[i]-Sum(s[j],s[j+1])|$
  注:Sum(x,y)=M[x]+M[y]$Sum(x,y)=M[x]+M[y]$
• 如果i$i$大于s[K]$s[K]$，误差为2×|M[i]−M[S[k]]|$2\times |M[i]-M[S[k]]|$

若最大允许的误差为E$E$ ,找出最小的一部分结果使得误差不超过E$E$。

---

思路：

吐槽：原题是真的玄学，根本看不懂。

好奇怪的一道题啊。害得我这次考试考了倒一。。。

---

正解:DP$DP$

题目都看不懂还打啥不会的DP
设f[i][j]$f[i][j]$表示第i−1$第i-1$点和第j+1$j+1$点都选，i$i$到j$j$这段区间的值。
方程：

f[k][j+1]=min(f[k][j+1],f[i][j]+t[i+1][k−1])$$f[k][j+1]=min(f[k][j+1],f[i][j]+t[i+1][k-1])$$

---

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const long long inf=1e17;
long long n,m,a[501],f[501][501],t[501][501];

long long abs(int x)
{
    return x>0?x:-x;
}

int main()
{
    scanf("%lld%lld",&n,&m);
    for (long long i=1;i<=n;i++)
     scanf("%lld",&a[i]);
    for (long long i=0;i<=n+1;i++)
     for (long long j=i+1;j<=n+1;j++)
      for (long long k=i+1;k<=j-1;k++)  //初始化每种情况的误差
      {
        if (!i) t[i+1][j-1]+=2*abs(a[k]-a[j]);
        if (i&&j<=n) t[i+1][j-1]+=abs(a[k]*2-(a[i]+a[j])); 
        if (j>n) t[i+1][j-1]+=2*abs(a[k]-a[i]);
      }
    memset(f,127/3,sizeof(f));
    f[0][0]=0;  //初始化
    for (long long i=0;i<=n;i++)
     for (long long j=0;j<=n;j++)
      for (long long k=i+1;k<=n+1;k++)
       f[k][j+1]=min(f[k][j+1],f[i][j]+t[i+1][k-1]);
    for (long long i=2;i<=n+1;i++)
     if (f[n+1][i]<=m)
      return printf("%lld %lld\n",i-1,f[n+1][i])&0;
}