POJ 1722 - SUBTRACT

http://poj.org/problem?id=1722

概要

数列 a = [a[1], ..., a[N]] が与えられる．手続き con() を

con(a,i) = [a[1], ..., a[i-1], a[i]-a[i+1], a[i+2], ..., a[N]]

と定義すると，N-1 回 con すると数列の大きさは1になる．

N-1 回 con したときに a = [T] となるような con に与える i の列 i[1], ..., i[N-1] を答える．

そのような数列は必ずあることが保証されており，最後が [T] になるような列ならばどんな列でもかまわない (Special Judge)．

制約

解法

con の操作について考えると，最終的に

a[1] - a[2] ± a[3] ± … ± a[N] = T

となるように N-2 個の ± を決定できればよいことがわかる．

これは典型的な DP により ( 2 * 10^4 ) * 100 程度で求められる．

±の割り当てがわかったら，+ に割り当てられた場所についてそのひとつ前から - で括り先に計算することで - のみの式にできる． そうしたら，あとは先頭から単に引けばよいので 1 を出力しつづければよい．

たとえば Sample Input の場合，DP によって

12 - 10 + 4 + 3 - 5 = 4

とわかる．+ の位置について上述の処理を行うと

12 - ((10 - 4) - 3) - 5 = 4

となり，このとき 2 2 を出力している．

あとは先頭から引けばよいので 1 1 を出力して終了．

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6   int N, T;
 7   cin >> N >> T;
 8   static int a[100];
 9   for (int i = 0; i < N; i++) {
10     cin >> a[i];
11   }
12 
13   static const int M = 10000;
14   static int dp[100][2*M+1];
15   dp[0][M+a[0]] = 1;
16   dp[1][M+a[0]-a[1]] = -1;
17   for (int i = 2; i < N; i++) {
18     for (int j = -10000; j <= 10000; j++) {
19       if (dp[i-1][j+M] != 0) {
20         dp[i][j+a[i]+M] = 1;
21         dp[i][j-a[i]+M] = -1;
22       }
23     }
24   }
25 
26   int t = T;
27   static int b[100];
28   for (int i = N-1; i > 0; i--) {
29     if (dp[i][t+M] == 1) {
30       t -= a[i];
31       b[i] = 1;
32     } else if (dp[i][t+M] == -1) {
33       t += a[i];
34       b[i] = -1;
35     }
36   }
37 
38   int c = 0;
39   for (int i = 1; i < N; i++) {
40     if (b[i] == 1) {
41       cout << i-c << endl;
42       c++;
43     }
44   }
45   for (int i = 1; i < N; i++) {
46     if (b[i] == -1) {
47       cout << "1" << endl;
48     }
49   }
50   return 0;
51 }
poj/1722.cc