第二次做自己学校OJ的题目，贡献了三个TLE,两个RE。。

其实这是一道非常非常经典的DP题。题目的意思，在标程里面写的很清楚了：从数列中选取若干个数，使其和与M的差的绝对值最小。

我开始想到的是那个分硬币的题。那种近乎暴力的方法，在这道题目上用，TLE了，因为这个数据的大小就是超了原来的想法，刚开始题目没看清楚，以为能过的。

现在简述一下解决这个问题：从数列中选取若干个数，使其和与M的差的绝对值最小 的思路。

我们用一个数组d[i][j]来表示/取到第i个数字时，在a[1],a[2]......,a[i]个中/任取若干个数/的和，使得/这个和/与j的差值/的绝对值/最小的时候/的这个差值。

当i=0时，d[0][j]=-j，因为一个都没取的时候，跟j的差值显然是j。这个就是边界条件了。

再看一般情况。这个时候的状态转移方程是dp(i,j)=min{dp(i-1,j),dp(i-1,j-a[j])【a[j]<j】,a[j]-j【a[j]>j】}

为了让自己更明白，自己给自己重新解释一遍：

当遇到第i个数字时，a[i]可以不取。这个时候dp(i,j)=dp(i-1,j)

如果取了，就要看j的大小了，所以dp(i,j)= dp(i-1,j-a[j])【a[j]<j】,a[j]-j【a[j]>j】

剩下的就是一些细节问题了，下面是代码：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 using namespace std; 5 int d[1001][1001];//dp数组 6 int a[1001];//记录每个氨基酸的分子量 7 int dp(int c,int w) 8 { 9     int &ans = d[c][w];10     if(ans != 2000)11         return ans;12     if(c == 0)13     {14         ans = -w;15         return ans;16     }17     else18     {19         int r = dp(c - 1,w);20         int t;21         if(a[c] < w)22             t = dp(c - 1,w - a[c]);23         else24             t = a[c] - w;25         if(abs(r) == abs(t))26         {27             if(r < 0)28                 ans = r;29             else30                 ans = t;31         }32         else33             ans = abs(r) < abs(t) ? r : t;34     }35     return ans;36 }37 int main()38 {39     int c,w;40     while(cin>>c>>w)41     {42         int i,j;43         for(i = 1;i <= c;i++)44         {45             cin>>a[i];46             a[i] -= 18;47         }48         for(i = 0;i <= c;i++)49             for(j = 0;j <= w - 18;j++)50                 d[i][j] = 2000;51         cout<<(w + dp(c,w - 18))<