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

大佬的思路： 这其实是一道“披着狼皮的背包题”

我们只需要对状态稍作调整就可以套背包啦~~~

我们先把骨牌翻转，调整至点数大的在上面

这样，我们就能保证上方的点数一定比下方大，并且保证每翻转一 次，都能使上下的点数之差变小，而变小的点数，就是上下点数之差乘以2。

把改变的点数看成物品的体积，初始上下方的点数之差看做背包体积，不难看出背包问题的模型。

那么物品的重量是什么呢？

因为我们一开始就把点数大的放在了上面，而每放一次，翻转次数就+1。考虑：要是我后来后悔了，我发现不翻这个骨牌更好怎么办？那我会把它翻回来，那么相当于没有翻这个骨牌。

因此，一开始翻过的骨牌重量就是-1，未翻过的骨牌重量就是1（重量等价于翻转次数）

当然，上下相同的骨牌就是体积为0，重量为0的物品，因为他们无论怎么翻，都不会对上下点数差造成影响。

至此，背包的模型就出来了。这个问题被简化成：有n个物品，给出每个物品的体积v[i],他们的重量是1或-1。背包的重量为base，体积为tot，现在请把这n个物品放到背包里去，总体积不能超过tot，体积最大的情况下使得物品重量之和最小。

其中，dp[i][j]表示前i件物品能装到体积为j的最小重量

vs[i][j]表示前i件物品能否装到j体积

代码如下：

#include
   
    using namespace std;int n;int sum;int v[1007],w[1007];int dp[1007][6007],vis[1007][6007];//不能用一维的数组进行求解，因为w数组中有正有负，可能出现结果为0而不好处理。int base;int main(){
       scanf("%d",&n);    int x,y;    for(int i=1;i<=n;i++)    {
           scanf("%d%d",&x,&y);        if(x>y)        {
               v[i]=2*(x-y);            w[i]=1;            sum+=x-y;        }        else if(x
    
     =1;i--)    if(vis[n][i])    {
           printf("%d\n",base+dp[n][i]);        return 0;    }    return 0;}
    
   

做法二：用dp[i][j]来表示当前考虑到第i个骨牌，第一行的总和为j的最小交换次数。记第一行骨牌的点数放入数组a，第二行骨牌的点数放入数组b，初始时令dp[1][a[1]]=0，dp[1][b[1]]=1。

状态转移方程为：dp[i][j]=min(dp[i][j],dp[i-1][j-a[i]]) dp[i][j]=min(dp[i][j],dp[i-1][j-b[i]]+1) 由于我们可以计算所有牌的总和，最终，再从所有的能通过交换使得第一行的所有总和中，找到使差值最小的。

#include
   
    using namespace std;const int inf=1e9;int n;int a[1007],b[1007];int dp[1007][6007];int sum;int main(){
       scanf("%d",&n);    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][b[1]]=1,dp[1][a[1]]=0;//这个顺序不能交换，因为当第一个牌相等时，一二行不用换    for(int i=2;i<=n;i++)    for(int j=0;j<=6*i;j++)    {
           if(j-a[i]>=0) dp[i][j]=min(dp[i][j],dp[i-1][j-a[i]]);        if(j-b[i]>=0) dp[i][j]=min(dp[i][j],dp[i-1][j-b[i]]+1);    }    int mi=inf,ans=inf;    for(int i=0;i<=sum;i++)    {
           if(dp[n][i]!=inf){
           if(abs(sum-2*i)
   

转载地址：http://vsgwi.baihongyu.com/