洛谷 P1282 多米诺骨牌("01"背包)

时间:2022-06-26 17:44:46

传送门

https://www.cnblogs.com/violet-acmer/p/9852294.html

参考资料:

  [1]:https://blog.csdn.net/Darost/article/details/52517823

题解:

  对于一个牌,无非就是翻转或者不翻转这两种情况,所以由此我们可以从决策入手

  设dp[i][j]为前i个骨牌差值为j的最小翻牌次数

  初始值全部赋值为INF;

  然后f[1][a[1]-b[1]]=0, f[1][b[1]-a[i]]=1;对应于第一张牌不翻和翻

  状态转移方程:

  f[i][j] = min(f[i-1][j-(a[i]-b[i])], f[i-1][j-(b[i]-a[i])]+1)]分别对应于不翻和翻

  由于有负数,要加上一个较大的中间数把所有的值转为正数,然后找答案在dp[n]里找,从较大的中间数开始双向查找,最早找到的就是答案。

学习笔记:

  此题难点在于状态转移方程的查找。 

  dp[ ][ ]的作用很巧妙,是我不曾想到的,初始思路只知道一个暴力,就是枚举所有的可能,从中查找最优解,时间复杂度高达O(2^n),指定不能高效求解。

  算法之路还很长,一步一步来吧

AC代码:

 #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
const int maxn=+; int n;
int a[maxn],b[maxn];
int dp[maxn][*maxn];
int mid=;//中间数 void Solve()
{
dp[][a[]-b[]+mid]=,dp[][b[]-a[]+mid]=;
for(int i=;i <= n;++i)
{
for(int j=-*n;j <= *n;++j)//查找dp[i][-5n,....,5n]的最优解
{
dp[i][j+mid]=min(dp[i][j+mid],dp[i-][j-(a[i]-b[i])+mid]);
dp[i][j+mid]=min(dp[i][j+mid],dp[i-][j-(b[i]-a[i])+mid]+);
}
}
for(int i=mid,j=mid;i <= *mid || j >= ;++i,--j)
if(dp[n][i] != INF)
{
printf("%d\n",dp[n][i]);
break;
}
else if(dp[n][j] != INF)
{
printf("%d\n",dp[n][j]);
break;
} }
int main()
{
scanf("%d",&n);
for(int i=;i <= n;++i)
scanf("%d%d",a+i,b+i);
mem(dp,INF);
Solve();
}