A[i] {ai | i->1...n}; ai->[1, 100];
B[i] {bi | i->1...n}; bi->[1, 100];
对每个i选择A[i] 或者B[i],使其总和与未选择的数字的总和差值最小,给出选择项.
#include<cstdio>
int A[101];
int B[101];
int sumCost;
int total;
int check[10001];
int pre[10001];
int Q[2][10001];
int nq;
int temp;
int n;
void input(int* in){
for(int i = 0; i < n; i++){
scanf("%d", &in[i]);
total += in[i];
}
}
void init(){
total = 0;
input(A);
input(B);
sumCost = 0;
for(int i = 0; i < n; i++){
sumCost += A[i] > B[i] ? A[i] : B[i];
}
}
void update(int i, int j, int* cost, int sel){
int I = Q[0][j] + cost[i];
if(!check[I]){
check[I] = 1;
pre[I] = Q[0][j];
Q[1][temp] = I;
temp++;
}
}
void bfs(){
int i = 0;
int j = 0;
for(i = 0; i <= sumCost; i++){
pre[i] = -1;
}
Q[0][0] = 0;
nq = 1;
for(i = 0; i < n; i++){
for(j = 0; j <= sumCost; j++){
check[j] = 0;
}
temp = 0;
for(j = 0; j < nq; j++){
update(i, j, A, 0);
update(i, j, B, 1);
}
nq = temp;
for(j = 0; j < nq; j++){
Q[0][j] = Q[1][j];
}
}
for(i = 0; i <= sumCost; i++){
check[i] = 0;
}
for(i = 0; i < nq; i++){
check[Q[0][i]] = 1;
}
}
void print(){
int i = 0;
int j = 0;
int d = 0;
int minD = total + 1;
int mid = -1;
for(i = 0; i <= sumCost; i++){
if(check[i]){
d = total - i;
d = (d < i) ? (i - d) : (d - i);
if(d < minD){
minD = d;
mid = i;
}
else{
break;
}
}
}
printf("%d\n", mid);
for(i = n - 1; i >= 0; i--){
temp = (-1 == pre[mid]) ? 0 : pre[mid];
temp = (A[i] == (mid - temp)) ? 0 : 1;
printf("%d %d\n", i, temp);
mid = pre[mid];
}
}
int main(int argc, char* argv[], char* env[])
{
while(scanf("%d", &n) != EOF){
init();
bfs();
print();
}
return 0;
}
posted on 2011-07-19 17:38
Lshain 阅读(181)
评论(0) 编辑 收藏 引用 所属分类:
DP 、
题解-杂