洛谷 1282 多米诺骨牌

本文主要是介绍洛谷 1282 多米诺骨牌，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://www.luogu.org/problem/show?pid=1282#
看了题解后明白的DP。。。
s1表示正差值的和，s2表示负差值绝对值的和，now表示初始值。
因为C++数组下标不能为负数，可以整体+s2，f[i]表示i-s2的最小翻转次数。
题解上说要讨论a[i]的正负，没讨论会被卡掉一个点，原因大概是当a[i]>0时
j-2*a[i]小于j，从小到大枚举可以保证无后效性，a[i]<0时同理。
因为一开始f[now+s2]=1，所以最后的结果要-1输出。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int f[10100],a[1010];
int s1,s2,n,x,y,now;
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&x,&y);a[i]=x-y;if(a[i]>0)s1+=a[i];elses2-=a[i];now+=a[i];}f[now+s2]=1;for(int i=1;i<=n;i++){if(a[i]>0){for(int j=a[i]*2;j<=s1+s2;j++)if(f[j]>0&&(f[j-a[i]*2]==0||f[j]+1<f[j-a[i]*2]))f[j-a[i]*2]=f[j]+1;}if(a[i]<0){for(int j=s1+s2;j>=a[i]*2;j--)if(f[j]>0&&(f[j-a[i]*2]==0||f[j]+1<f[j-a[i]*2]))f[j-a[i]*2]=f[j]+1;}}int i=s2,j=s2;while(f[i]==0&&f[j]==0){i++;j--;}if(a[i]==0)printf("%d",f[j]-1);elseprintf("%d",f[i]-1);return 0;
}

这篇关于洛谷 1282 多米诺骨牌的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---