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).
制約
- 1 <= N <= 100
- -10^4 <= T <= 10^4
- 1 <= a[i] <= 100
解法
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
を出力して終了.
poj/1722.cc1 #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 }