我..莫名其妙搞出来的

随便搞搞..幻想中的dp结果对了

我也很迷茫

 

Description

• 为了研究农场的气候,Betsy帮助农夫John做了N(1 <= N <= 100)次气压测量并按顺序记录了结果M_1...M_N(1 <= M_i <= 1,000,000).

  Betsy想找出一部分测量结果来总结整天的气压分布. 她想用K(1 <= K <= N)个数s_j(1 <= s_1 < s_2 < ... < s_K <= N)来概括所有测量结果. 她想限制如下的误差:对于任何测量结果子集,每一个非此子集中的结果都会产生误差.总误差是所有测量结果的误差之和.更明确第说, 对于每一个和所有s_j都不同的i:
  　　* 如果 i 小于 s_1, 误差是:2 * | M_i - M_(s_1) | 
  　　* 如果i在s_j和s_(j+1)之间,误差是:| 2 * M_i - Sum(s_j, s_(j+1)) |     注:Sum(x, y) = M_x + M_y; (M_x 和 M_y 之和)
  　　* 如果i大于s_K,误差为:2 * | M_i - M_(s_K) |
  　　Besty给了最大允许的误差E (1 <= E <= 1,000,000),找出最小的一部分结果使得误差最多为E.

Input

• 第一行: 两个空格分离的数: N 和 E

  第2..N+1行: 第i+1行包含一次测量记录:M_i

Output

• 第一行: 两个空格分开的数: 最少能达到误差小于等于E的测量数目 和 使用那个测量数目能达到的最小误差

Sample Input

• 4 20

　10 3

　20 40

Sample Output

• 2 17

Hint

• 【样例说明】

　　　　选择第二和第四次测量结果能达到最小误差17. 第一次结果的误差是2*|10-3| = 14;第三次结果的误差是|2*20 - (3+40)|=3.

 

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 int n,e; 7 long long m[110],ero[110][110],dp[110][110];//ero选i和j产生的误差//dp以j结尾的时候，有i个最少测量数目 能达到的最小误差  8 long long abss(long long a) 9 {10     if(a<0)return -a;11     return a;12 }13 int main()14 {15     int i,j,k;16     scanf("%d%d",&n,&e);17     for(i=1;i<=n;i++)scanf("%lld",&m[i]);    18     long long ans=n,anss=999999999;19     20     for(k=1;k<=n;k++)21     {22         for(i=k+1;i<=n;i++)23             for(j=k+1;j<=i-1;j++) /*枚举题中的i*/ ero[k][i]+=abss(2*m[j]-m[i]-m[k]);24             25         for(i=1;i