| ||||||||||
| 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