题解 2183: 多米诺骨牌 （c++代码）

解题思路:
    原博客地址在此！

参考代码:

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1000 + 10;
const int INF = 0x3f3f3f3f;


int n,s = 0;
int a[maxn],b[maxn],dp[maxn][maxn*6+10];
int main(){
  scanf("%d",&n);
  for(int i = 1; i <= n; i++)
  {
    scanf("%d%d",&a[i],&b[i]);
    s += a[i] + b[i];
  }
  memset(dp,INF,sizeof(dp));
  dp[1][a[1]] = 0; dp[1][b[1]] = 1;
  for(int i = 2; i <= n; i++)
   for(int j = 0; j <= 6*n; j++)
     {
       if(j >= a[i]) dp[i][j] = min(dp[i][j],dp[i-1][j-a[i]]);
       if(j >= b[i]) dp[i][j] = min(dp[i][j],dp[i-1][j-b[i]] + 1);
     }
  int ans = INF,anst = INF;
  for(int j = 0; j <= s; j++)
    if(dp[n][j] < INF)
     if(anst > abs(s-j-j))
      anst = abs(s-j-j), ans = dp[n][j];
    else if(anst == abs(s-j-j)) ans = min(ans,dp[n][j]);

  printf("%d\n",ans);
  return 0;
 }