借鉴自洛谷题解
本题是一个背包问题。是一类求两集合之间的差关系的动规问题。可以将求最值转变为求可行性
背包问题是要建立起体积和重量之间的关系
我们尝试根据题目所给条件转化为背包问题，首先统一将大的放在上面，那么势必会进行几次翻转，我们记录这些翻转的数量，作为背包的初始重量。
因为我们所要求的是最小翻转次数，所以我们将这个设计为物品重量，根据背包的要求，所求的就是重量
那么剩下需要考虑的是体积，显然我们发现剩下题目给定条件，只有点数是没有利用过的，显然我们只能用点数来作为背包问题的体积
已知翻转一张牌需要变化2*（x-y），所以这个就是物品体积。那么背包体积就是原来的差值总数，而我们要求的就是，能装的体积最大的时候的最小重量
为什么是体积最大？ 因为初始是最大差值，我们需要求的上下最小差值，所以体积越大就意味着差值缩小的越大。
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+5; const int inf=0x3f3f3f3f; int dp[1005][6005]; bool vs[1005][6005]; int w[1005]; int v[1005]; int main(){ int n,i,j,x,y,base=0,tot=0; scanf("%d",&n); memset(dp,0x3f,sizeof dp); dp[0][0]=0; for(i=1;i<=n;i++) { scanf("%d%d",&x,&y); if(x>y){ v[i]=2*(x-y); w[i]=1; tot+=x-y; } if(y>x) { v[i]=2*(y-x); w[i]=-1; tot+=y-x; base++; } } for(i=1;i<=n;i++){ for(j=0;j<=tot;j++){ dp[i][j]=dp[i-1][j]; if(j>=v[i]) dp[i][j]=min(dp[i][j],dp[i-1][j-v[i]]+w[i]); } } int res=0; for(i=tot;i>=0;i--){ if(dp[n][i]<inf/2) break; } printf("%d",base+dp[n][i]); }
原文：https://www.cnblogs.com/ctyakwf/p/12222734.html
