洛谷P1282 多米诺骨牌【线性dp】-白红宇

洛谷P1282 多米诺骨牌【线性dp】

阅读量：4472 次

发布时间：2019-06-08

本文共 1247 字，大约阅读时间需要 4 分钟。

题目：

题意：

给定n个牌，每个牌有一个上点数和下点数。可以通过旋转改变交换上下点数。

问使得上点数之和和下点数之和的差的绝对值最小的最少旋转方法。

思路：

新增一个牌，对于点数差的贡献是+a-b或-a+b

所以很自然的可以写出状态转移方程dp[i][s]=min(dp[i-1][s-a+b], dp[i-1][s+a-b]+1)

需要注意的是第二维放的是差，有可能是负数，所以要加一个偏移量。

而s的范围应该没有限制，从最小到最大值。

最后在0~最大值中寻找一个最小的s（表示的是绝对值），使得dp[n][s]或dp[n][-s]是有值的，就是答案。

1 #include
     
       2 #include
      
        3 #include
        4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              
               11 #include
               
                12 13 #define inf 0x7fffffff14 using namespace std;15 typedef long long LL;16 typedef pair
                
                  pr;17 18 int n;19 const int maxn = 1005;20 const int mx = 7000;21 int a[maxn], b[maxn];22 int dp[maxn][mx * 2];23 24 int main()25 {26 scanf("%d", &n);27 for(int i = 1; i <= n; i++){28 scanf("%d%d", &a[i], &b[i]);29 }30 memset(dp, 0x3f, sizeof(dp));31 32 dp[0][mx] = 0;33 for(int i = 1; i <= n; i++){34 for(int j = -mx; j <= mx; j++){35 dp[i][j + mx] = min(dp[i - 1][j - a[i] + b[i] + mx], dp[i - 1][j + a[i] - b[i] + mx] + 1);36 }37 }38 39 for(int i = 0; i <= mx; i++){40 int ans = min(dp[n][i + mx], dp[n][-i + mx]);41 if(ans < mx){42 printf("%d\n", ans);43 break;44 }45 }46 47 return 0; 48 }