P1282 多米诺骨牌 dp

思路：dp[i][j] 的j是上半段的和的值   这里表示的是达到上半段值是j的最小次数

答案在最小的可达到的j

#include<bits/stdc++.h>
using namespace std;
const int INF=10000000;
int a[10000],b[10000];
int dp[1000+10][10000];
const int pianyi=5000;
int main(){
int n;cin>>n;
int sum=0;
for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]),sum+=a[i]+b[i];
   for (int i = 1; i <= n; i ++)
        for (int j = 0; j <= 6*n; j ++) dp[i][j] = INF;
   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 temp1=INF,ans=INF;
   for(int i=0;i<=sum;i++){
       if(dp[n][i]!=INF){
              if(abs(2*i-sum)<temp1){
                  ans=dp[n][i];
                  temp1=abs(2*i-sum);
              }
             else if(abs(i-(sum-i)) == temp1)ans=min(ans,dp[n][i]);
       }
   }
   cout<<ans<<endl;
    return 0;
}