多米诺骨牌.cpp

背包类问题浅析和一些背包类问题的解答源程序。

#include <iostream>
using namespace std;

const int N = 1009, D = 5010, T = 10011, S = 10, M = 10100;
int n, b[N], s=D, f[2][M]={0}, cur=0, pre=1;
bool can[2][M]={0};

int main(){
    cin >>n;
    int i, j, k;
    for( k=1; k<=n; ++k ){
         cin >>i >>j;
         b[k] = j+j-i-i;
         s += i - j;
    }
    can[cur][s] = true;
    
    for( i=1; i<=n; ++i ){
         cur = pre;   pre = 1 - pre;
         memcpy( can[cur], can[pre], sizeof(can[pre]) );
         memcpy( f[cur], f[pre], sizeof(f[pre]) );
         for( j=S; j<T; ++j )
              if( can[pre][j] ){
                  if( !can[cur][j+b[i]] ){
                      can[cur][j+b[i]] = true;
                      f[cur][j+b[i]] = f[pre][j] + 1;
                  }
                  else if( f[cur][j+b[i]] > f[pre][j] + 1 )
                           f[cur][j+b[i]] = f[pre][j] + 1;
              }
    }
    
    for( i=D; (!can[cur][i]) && (i<T); ++i );
    for( j=D; (!can[cur][j]) && (j>0); --j );
    if( i-D < D-j ) cout <<f[cur][i] <<endl;
    else if ( i-D > D-j ) cout <<f[cur][j] <<endl;
    else cout <<( f[cur][i] < f[cur][j] ? f[cur][i] : f[cur][j] ) <<endl;
    
    system( "pause" );
    return 0;
}