1942.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1942 on 2006-07-23 at 15:26:05 */ 
#include <stdio.h>

int main()
{
    char a[50][16][16][16][5], *b;
    int wm[50], wn[50], wp[50];
    int m, n, p, N;
    int i, j, k, l, flag;
    
    while(scanf("%d %d %d", &m, &n, &p) == 3) {
        if((m == 0) && (n == 0) && (p == 0)) {
            return 0;
        } else {
            scanf("%d", &N);
            for(i = 0; i < N; i++) {
                scanf("%d %d %d", &wm[i], &wn[i], &wp[i]);
            }
            for(i = N-1; i >= 0; i--) {
                for(j = 0; j <= m; j++) {
                    for(k = 0; k <= n; k++) {
                        for(l = 0; l <= p; l++) { 
                            if(j < wm[i] || k < wn[i] || l < wp[i]) {
                                if(i == N-1) {
                                    a[i][j][k][l][0] = 0;
                                    a[i][j][k][l][4] = 0;
                                } else {    
                                    a[i][j][k][l][0] = a[i+1][j][k][l][0];
                                    a[i][j][k][l][1] = j;
                                    a[i][j][k][l][2] = k;
                                    a[i][j][k][l][3] = l;
                                    a[i][j][k][l][4] = 0;
                                }    
                            } else {
                                if(i == N-1) {
                                    a[i][j][k][l][0] = 1;
                                    a[i][j][k][l][4] = 1;
                                } else {    
                                    if(a[i+1][j][k][l][0] < a[i+1][j-wm[i]][k-wn[i]][l-wp[i]][0] + 1) {
                                        a[i][j][k][l][0] = a[i+1][j-wm[i]][k-wn[i]][l-wp[i]][0] + 1;
                                        a[i][j][k][l][1] = j-wm[i];
                                        a[i][j][k][l][2] = k-wn[i];
                                        a[i][j][k][l][3] = l-wp[i];
                                        a[i][j][k][l][4] = 1;
                                    } else {
                                        a[i][j][k][l][0] = a[i+1][j][k][l][0];
                                        a[i][j][k][l][1] = j;
                                        a[i][j][k][l][2] = k;
                                        a[i][j][k][l][3] = l;
                                        a[i][j][k][l][4] = 0;
                                    }    
                                }
                            }    
                        }    
                    }    
                }
            }
            printf("%d\n", (int)a[0][m][n][p][0]);
            if(a[0][m][n][p][0] != 0) {
                flag = 0;
                b = a[0][m][n][p];
                for(i = 0; i < N; i++) {
                    if(b[4] == 1) {
                        if(flag == 1) {
                            putchar(' ');
                        }
                        printf("%d", i+1);
                        flag = 1;
                    }
                    if(i != N-1) {
                        b = a[i+1][b[1]][b[2]][b[3]];
                    }    
                }
                putchar('\n');
            }    
        }
    }

    return 0;
}