Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
DP附代妈,992K16ms#include <iostream> #include <stdio.h> using namespace std; int trace[2016][2016]; int MAX(int a, int b){ return a>b ? a : b; } int main() { while(1){ int M, L; scanf("%d%d", &M, &L); if(M == 0 && L == 0) return M+L; int N; scanf("%d", &N); int boxes[2016]; int sum = 0; for(int i = 1; i <= N; i++){ scanf("%d", boxes+i); sum += *(boxes+i); } if(sum > M+L){ printf("Impossible to distribute\n"); continue; } int lower = sum - L, upper = M; trace[0][0] = 0; for(int i = 1; i <= upper; i++){ trace[0][i] = -1; } for(int i = 1; i <= N; i++){ for(int j = 0; j <= upper; j++){ if(j < boxes[i]){ if(trace[i-1][j] != -1) trace[i][j] = 0; else trace[i][j] = -1; } else{ if(trace[i-1][j] != -1) trace[i][j] = 0; else if(trace[i-1][j-boxes[i]] != -1) trace[i][j] = 1; else trace[i][j] = -1; } if(trace[i][j] != -1 && j >= lower){ int temp[2004]; int tempNum = 0; int k = i; int l = j; while(k > 0){ if(trace[k][l] == 1){ temp[tempNum] = k; tempNum ++; l -= boxes[k]; } k --; } printf("%d ", tempNum); for(int s = tempNum - 1; s >= 0; s--){ printf("%d ", temp[s]); } printf("\n"); goto done; } } } printf("Impossible to distribute\n"); done: continue; } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator