posts - 2,  comments - 3,  trackbacks - 0
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题解-杂
<2024年9月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
293012345

常用链接

留言簿

文章分类(46)

文章档案(33)

ACM

Algorithm Link

BLOG

Format analysis

Forum

Math

mirror

OpenGL

Protocol Analyzer

Recent Contests

Search

WIN32 Programming

最新随笔

搜索

  •  

最新评论

阅读排行榜

评论排行榜