贵有恒，何必三更起五更眠；最无益，莫过一日曝十日寒。

 【动态规划】多米诺骨

时间限制: 1 Sec  内存限制: 128 MB

题目描述

多米诺骨牌有上下2个方块组成，每个方块中有1~6个点。现有排成行的n个多米诺骨牌如下图所示。    

上方块中点数之和记为Σ

₁ ，下方块中点数之和记为Σ

₂ ，它们的差为|Σ

₁-Σ

₂| 。例如上图中， Σ

₁=6+1+1+1=9， Σ

₂=1+5+3+2=11，|Σ

₁-Σ

₂| =2。每个多米诺骨牌可以旋转180°，使得上下两个方块互换位置。

编程用最少的旋转次数使多米诺骨牌上下2行点数之差达到最小。

对于图8-1中的例子，只要将最后一个多米诺骨牌旋转180°，可使上下2行点数之差为0。

输入

第一行是一个正整数n(1≤n≤1000)，表示多米诺骨牌数。接下来的n行表示n个多米诺骨牌的点数。每行有两个用空格隔开的正整数，表示多米诺骨牌上下方块中的点数a和b，且1≤a，b≤6。

输出

仅一行，包含一个整数。表示求得的最小旋转次数。

样例输入

46 11 51 31 2

样例输出

1 分析：因为存在骨牌上减下为负数的时候，把数组要多开一倍。dp[x]表示和为x的时候最少的交换次数 dp[j+a]=min(dp[j+a],dp[j]); dp[j+b]=min(dp[j+b],dp[j]+1);

#include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              using namespace std;const int maxn = 12010;int dp[maxn], n;int main(){    int a,b,sum=0,i,j;    cin>>n;    for(int i=1;i
              
               >a>>b; sum+=a+b; for(j=sum;j>=0;j--) { int t=dp[j]; dp[j]=200000; dp[j+a]=min(dp[j+a],t); dp[j+b]=min(dp[j+b],t+1); } } sum=sum/2; for(i=sum;i>=0;i--) if(dp[i]<=n) break; for(j=sum;j