首页 > 代码库 > {POJ}{3971}{Scales}{O(N)动态规划}
{POJ}{3971}{Scales}{O(N)动态规划}
题意:给定一堆2二进制砝码,给定一个物品,要求在天平两端加入物品和砝码使之平衡,求可能数。
思路:一开始想到了直接用数学原理,结果没证出来。做如下思考,此题需要用二进制:
(1)设物品重量为w,加入的砝码重量为x,另一边重量为y,便有w+x=y。
(2)另外,假如物品为100110,加入的砝码可以为000010,那么总和为101000,显然x与y不能有位数相同的1(因为每种砝码只有一个),因此便有x&y=0
依据这两点,可以知道此题的关键之处就在于如何分析w+x的进位情况。分析物品的第i位,比如为1,那么如果前面的一位没有进位,那么他便可以加上1或者不加;如果进位,那就肯定不能加1(因为加1以后与进位的1加上这一位的结果还是1,与x&y=0矛盾),所以对于每一位,它的进位与不进位情况需要分开判断。
DP思路:设f[i][0]表示判断到i位时它不进位的情况数,f[i][1]表示到i位时它进位的情况数,都是从低位到高位判断。
(1)先考虑f[i][0](不进位的情况)
- i位为1,如果前面不进位,那么这一位只能加上0才满足不进位的情况;如果前面进位,那么无论如何不可能使这一位不进位,因此f[i][0]=f[i-1][0];
- i位为0,如果前面不进位,那么这一位只能选择0(因为选择加1的话将会与x&y=0矛盾);如果前面进位,那么这一位也只能选择0才能使i位也不进位,因此有f[i][0]=f[i-1][0]+f[i-1][1];
(2)再考虑f[i][1](进位的情况)
- i位为1,如果前面不进位,那么这一位只能选择1才能使i位进位;如果前面进位,那么只能选择0使之进位(如果选择1那么结果将会与x&y=0矛盾),因此f[i][1]=f[i-1][0]+f[i-1][1];
- i位为0,如果前面不进位,那么这一位无论如何不可能进位;如果前面进位,那么只能选择1才能使i位进位,因此f[i][1]=f[i-1][1];
这样,DP方程就得到了
if(s[i] == 1){ f[i][0] = f[i-1][0]; f[i][1] = f[i-1][0]+f[i-1][1];}else{ f[i][0] = f[i-1][0]+f[i-1][1]; f[i][1] = f[i-1][1];}
注意:不得不说,这个题目挺不错的,此题中间结果可能会超出long long,因此需要分次数判断,因为这个点我WA了N次
#include <iostream>#include <string>#include <cstring>#include <cstdio>#include <algorithm>#include <memory>#include <cmath>#include <bitset>#include <queue>#include <vector>#include <stack>using namespace std; #define CLR(x,y) memset(x,y,sizeof(x))#define MIN(m,v) (m)<(v)?(m):(v)#define MAX(m,v) (m)>(v)?(m):(v)#define ABS(x) ((x)>0?(x):-(x))#define rep(i,x,y) for(i=x;i<y;++i)const int MAXN = 1100000;int t,n,m,d;int s[MAXN];int dp[MAXN][2];void Solve(){ char c; scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&m,&d); getchar(); CLR(s,0); for(int i = m-1; i >= 0; --i){ scanf("%c",&c); s[i] = c-‘0‘; } if(s[0] == 0) { dp[0][0] = 1; dp[0][1] = 0; } else{ dp[0][0] = 1; dp[0][1] = 1; } for(int i = 1; i < n; ++i){ if(s[i] == 1){ dp[i][0] = dp[i-1][0]; dp[i][1] = dp[i-1][0]+dp[i-1][1]; } else{ dp[i][0] = dp[i-1][0]+dp[i-1][1]; dp[i][1] = dp[i-1][1]; } if(dp[i][0]>=d) dp[i][0]-=d; if(dp[i][1]>=d) dp[i][1]-=d; } cout<<(dp[n-1][0])<<endl; }}int main(){ Solve(); return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。