// POJ1014
// T = O(sum), 'sum' is the summary of all values
// You can optimaze it, such as reduce the size of 'can' by checking in someway
#include <iostream>
#include <cstring>
using namespace std;

int a[7], s[7];
char can[120100];

bool solve() {
    s[0] = 0;
    for (int i = 1; i <= 6; i++) {
        s[i] = a[i] * i + s[i - 1]; // 's[i]' is the summary of the values of the marble(s) of which the value is no more than 'i'
    }
    if (s[6] % 2) return false;    
    memset(can, 0, sizeof(char) * (s[6] + 1));
    can[0] = 1;
    for (int i = 1; i <= 6; i++) {
        if (a[i]) {
            int ss = s[i] - s[i - 1];
            for (int k = s[i - 1] ; k >= 0; k--)
                if (can[k]) can[k + ss] = 2; // mark every end of loop by 2, the loop is on the number of marble(s) of the value 'i'
            for (int j = 0; j < i; j++) {
                int n = 0; // n is a loop counter, the loop is on the number of marble(s) of value i
                for (int k = s[i] - j; k >= 0; k -= i) { // attention!! here is 'k -= i', this is the the reason why 'for j = 0 to i'
                    if (can[k] == 2) {can[k] = 1; n = a[i];} // refresh the end of loop
                    else if (n > 0) {can[k] = 1; n--;} // loop
                }
            }
        } // end of 'if(a[i])'
    }
    return can[s[6] / 2];
}

int main() {
    int CASE = 0;
    for (;;) {
        for (int i = 1; i <= 6; i++)
            cin >> a[i];
        if (a[1] == 0 && a[2] == 0 && a[3] == 0 && a[4] == 0 && a[5] == 0 && a[6] == 0) break;
        printf("Collection #%d:\nCan%s be divided.\n\n", ++CASE, solve() ? "" : "'t");
    }
    return 0;
}

• 上好的程序，读起来就是不一样！ (0) 123234345 2009-08-07 20:57:25