poj1722

题意：给定n个数，每次可对一相邻的数进行合并，合并的操作为a[i] -a[i+1]

操作完形成n-1数，在进行同样操作，最后只剩下一个数。。为给定的值。。

求如何操作。。

思路：dp

因为只能用-号，而减完得数等下再减去他，--就为+了。。

这样实质就是往里面添加+ 或-。。

就变成了背包问题了。。

 1 /*
 2   State:Accepted
 3   Time:2013-03-10 02:03:30
 4 */
 5 #include <iostream>
 6 #include <fstream>
 7 #include <cstring>
 8 #include <string>
 9 #include <algorithm>
10 #include <cmath>
11 int a[110] , b[105] , n , m;
12 bool f[105][20020];
13 
14 void dp(){
15     scanf("%d%d",&n , &m);
16     m += 10000;
17     for (int i = 1; i <= n ; ++i)
18         scanf("%d",&a[i]);
19     memset(f,  0 ,sizeof(f));
20     f[1][10000 + a[1]] = true;
21     f[2][10000 + a[1] - a[2]] = true;
22     for (int i = 3; i <= n ;  ++i)
23       for (int j = 0;  j <=20000 ; ++j){
24           if (j - a[i] >= 0) f[i][j] = f[i][j] || f[i - 1][j - a[i]];
25           if (j + a[i] <= 20000) f[i][j] = f[i][j] ||  f[i - 1][j + a[i]];
26       }
27       
28     for (int i = n; i >= 1; --i)
29         if (f[i - 1][m + a[i]]) {
30               b[i - 1] = -1;
31               m += a[i];
32         } else {
33                  b[i - 1] = 1;
34                  m -= a[i];
35                }
36     int k = 0;
37     for (int i = 1; i <= n - 1; ++i)
38        if (b[i] == 1) { 
39            printf("%d\n", i - k);
40            ++k;
41        }
42     for (int i = 1; i <= n -1 ; ++i)
43       if (b[i] == -1) printf("1\n");
44 }
45 int main(){
46      freopen("poj1722.in","r",stdin);
47      freopen("poj1722.out","w",stdout);
48      dp();
49      fclose(stdin);  fclose(stdout);
50 }