【按位考虑DP】代码源每日一题div1 2023.02.02 与

缺乏、安全感 2024-03-27 11:42 48阅读 0赞

[与 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge]

**这太酷了，很符合我对DP的想象**

**这DP太妙了，我还没做过这种按位考虑DP的题**

题意：

![3d56ef8ff87e1b159e1783587f898fd0.png][]

思路：

首先看第二个条件，一个数与后面的那个数与了之后还是后面那个数，这说明什么

我们按位考虑，比如这样：

10010111

10000101

这样就是满足条件的

归纳一下就是：对于n个数每一位，都是前面几个数是1，后面几个数是0

![73d7072e1c203db2ce33a25d7bbac685.png][]

然后我们去从高位到低位去考虑DP（低位到高位也可以，不影响，只不过习惯从高到低了）

状态设计：

**像这种计数类的DP，在设计状态时，考虑转移时需要考虑的量，即限制条件**

限制条件是和，因此加一维

设dp\[i\]\[j\]为考虑第i位，前i位的和为j的方案数

这样设计显然是不重不漏的

状态转移：

当然是从前一位转移过来

![aa13d91594933c6205f13090400fa38f.png][]

先去枚举阶段（位），然后去枚举1和0的分界线，然后去枚举和，转移就好了

注意在枚举和的时候，要注意上下界

上界就是K，下界是第i位是1，前面的位都是0产生的和

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    #define Please_ac return 0 
    #define y1 Y1
    const int mxn=1e4+10;
    const int mod=1e9+7;
    int n,K;
    int dp[33][mxn];
    void solve(){
        cin>>n>>K;
        dp[31][0]=1;
        for(int j=30;j>=0;j--){
            for(int i=0;i<=n;i++){
                int w=i*(1<<j);
                for(int k=K;k>=w;k--){
                    dp[j][k]+=dp[j+1][k-w];
                    dp[j][k]%=mod;
                }
            }
        }
        cout<<dp[0][K]<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();Please_ac;
    }

[- _ - Daimayuan Online Judge]: http://oj.daimayuan.top/problem/155
[3d56ef8ff87e1b159e1783587f898fd0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/b8db303199b04c7d9eafac9362465ce6.png
[73d7072e1c203db2ce33a25d7bbac685.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/b72496f2d1e940a1b53177da6bda0122.png
[aa13d91594933c6205f13090400fa38f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/22e2e452b09449f0a98b99b315786976.png