JZOJ 1293. 气象牛

题目

 

 

 

 

 

分析

 

• 我们可以用DP
• 设f[i][j]为前i个用了j个，所产生的最小误差
• 直接上n^3
• 预处理出每个点在另一个点前 后 中的值

代码

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 #define ll long long
 7 using namespace std;
 8 int a[201];
 9 int dis[201][201];
10 int f[201][201];
11 int ans[201];
12 int main()
13 {
14     int n,e;
15     scanf("%d%d",&n,&e);
16     for (int i=1;i<=n;i++) scanf("%d",&a[i]);
17     for (int i=0;i<=n+1;i++)
18      for (int j=i+1;j<=n+1;j++)
19       for (int k=i+1;k<=j-1;k++)
20       if (i==0) dis[i+1][j-1]+=abs(2*a[k]-2*a[j]); else
21       if (j==n+1) dis[i+1][j-1]+=abs(2*a[k]-2*a[i]); else
22       dis[i+1][j-1]+=abs(2*a[k]-a[i]-a[j]);
23     memset(f,0x3f,sizeof(f));
24     f[0][0]=0;
25     for (int i=0;i<=n;i++)
26       for (int j=0;j<=n;j++)
27       {
28            if (f[i][j]<=e)
29            {
30                for (int k=i+1;k<=n+1;k++)
31               f[k][j+1]=min(f[k][j+1],f[i][j]+dis[i+1][k-1]);
32          }
33       }
34     for (int i=2;i<=n+1;i++)
35     {
36         if (f[n+1][i]<=e)
37         {
38             cout<<i-1<<" "<<f[n+1][i]; return 0;
39         }
40
41     }
42
43 }