本文主要是介绍poj 3971 Scales （dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：
给你一个重量为w的物品 和 重量分别为 1 2 4 ... 2^(n-1) 的砝码，问 一共有多少种方式使得天平平衡。
解题思路：
让我们求的 就是 w + x = y 并且 x 与 y 在二进制形式下没有相同位置为 1 即 x & y = 0
一开始，我希望用数学公式推出来，但是失败了。后来查看了别人的题解，发现这是一道 动态规划。
我们设 dp[i][j] 表示 第i位，是否需要进位。并且，dp从低位往高位推比较好。
对于一个给定的 w 。如果他的第i位为0，x的第i位为0，可以选择从i+1位进位，也可以选择不进位，此时第i位均不进位；如果他的第i位为0，x的第i位为1，只能选择从i+1位进位，此时第i位进位（如果不进位，那么y的第i位也是1，与x&y=0矛盾）。同理，我们可以得到w的第i位为1，x的第i位为0的时候，可以选择从i+1位进位，此时第i位进位，也可以选择从i+1位不进位，此时第i位不进位（因为此时x的第i位为0，所以即使y的第i位也为0，x&y=0依然成立）；当w的第i位为1，x的第i位为1的时候，第i位肯定进位，而且第i+1位不能进位。
除此之外，我们需要对w = 0 的时候进行特判。因为当w=0 时，答案=0；
具体，代码如下：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
// w + x = y x & y = 0
int dp[1000009][3];
int main()
{int T,n,m,i,j,l,d;char w[1000009];scanf("%d",&T);while(T--){scanf("%d%d%d",&n,&l,&d);scanf("%s",w+(n-l));if(w[n-l]=='0'){printf("0\n");continue;}for(i=0; i<(n-l); i++)//统一起见，把w的位数与给定砝码的最大位数统一。不足用0补充w[i]='0';memset(dp,0,sizeof(dp));dp[n][0]=1;for(i=n-1; i>=0; i--){if(w[i]=='0'){//x的当前位为 0dp[i][0]+=dp[i+1][0]+dp[i+1][1];//x的当前位为 1dp[i][1]+=dp[i+1][1];}else if(w[i]=='1'){//x的当前位为 0dp[i][0]+=dp[i+1][0];dp[i][1]+=dp[i+1][1];//x的当前位为 1dp[i][1]+=dp[i+1][0];}dp[i][0]%=d;dp[i][1]%=d;}printf("%d\n",dp[0][0]);}return 0;
}
这篇关于poj 3971 Scales （dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
