博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Our happy ending
阅读量:5843 次
发布时间:2019-06-18

本文共 2763 字,大约阅读时间需要 9 分钟。

  • 题意:
    输入n、k、L,n个数,最大值不超过L,在序列中取若干个数和能达到k的序列个数
    n,k<=20 , 0<=L<=10^9
  • 分析:
    题目关键在于和k比較小,所以能够考虑DP。
    先说一下自己比赛时候想到的DP状态。好久才发现错了。

    。。。

    DP[i][j]表示当前是序列中的第i个数(必须选),和能取到j的序列个数。

    这个状态的问题就是在于反复:对于一个确定的序列来说,由于能够选取某些数字来求和,所以对于DP[i]来说,同一个序列能够得到非常多不同的和j,也就是被计算了非常多次从而导致反复。

    对照一下之前见过的一个类似的问题,给定一个序列。问取若干个数能达到和k的方案数:DP[i][j]表示当前是序列中的第i个数(必须选),和能取到j的序列个数,这个问题这样表示就是正确的了。
    为什么会这样呢?就是由于答案的推断方式不同:第一个问题的答案推断是,当前序列假设能取到若干个数使得和为k。那么答案加一;第二个问题则是,假设有x种方案。从当前序列中取出若干个数使得和为k。那么答案加x。也就是说。第一个问题的推断根据是序列是否满足,第二个则是取出来的集合是否满足。而上述DP的方案事实上就是在选择集合中的元素,由于DP[i][j]表示i必须选,也就是在集合中存在。
    那么到此,怎样推断一个序列是否是满足的呢:从左到右枚举序列当前位置的值,那么要求当前序列是否是满足的也就是求和能否到k,那么不可缺少的须要记录一下当前序列所能到达的和都有谁。至此。就能够用状压DP来解了。叙述一下二进制代表的意义:第一个1代表和为1。第二个1表示和为2……
    反思一下程序写的时候的问题:没实用滚动数组,导致错了非常多次。

    因为这个题目的状态转移仅仅会向更大的状态值(也能够是自己)转移。所以能够不採用滚动数组,一维解决。

    可是这样就须要额外注意一个问题。自己转移到自己的问题。因为这里理解的不是非常好。导致一直查不出来BUG。学习了。

const int MAXN = 21;int dp[1 << MAXN];int main(){    int T, n, sum, Max;    RI(T);    FE(kase, 1, T)    {        RIII(n, sum, Max);        int Min = min(sum, Max);        int all = 1 << sum;        CLR(dp, 0); dp[0] = 1;        REP(i, n)        {            FED(j, all - 1, 0)            {                if (dp[j] == 0)                    continue;                int x = dp[j];                for (int k = 1; k <= Min; k++)                {                    int nxt = j | ((j << k) & (all - 1)) | (1 << (k - 1));                    dp[nxt] += x;                    if (dp[nxt] >= MOD)                        dp[nxt] -= MOD;                }                if (Max - Min > 0)                    dp[j] = (dp[j] + 1LL * (Max - Min) * x) % MOD;            }        }        int ans = 0;        FF(i, 1 << (sum - 1), all)        {            ans += dp[i];            if (ans >= MOD)                ans -= MOD;        }        WI(ans);    }    return 0;}
用dp[1]表示0的方法,事实上不好。由于3(11)和2(10)表示的意义是一样的,并且不含或者包括零(第一个一)没有什么意义
const int MAXN = 21;int dp[1 << MAXN];int main(){    int T, n, sum, Max;    RI(T);    FE(kase, 1, T)    {        RIII(n, sum, Max);        int Min = min(sum, Max);        int all = 1 << (sum + 1);        CLR(dp, 0); dp[1] = 1;        REP(i, n)        {            FED(j, all - 1, 1)            {                if (dp[j] == 0)                    continue;                int x = dp[j];                for (int k = 1; k <= Min; k++)                {                    int nxt = j | ((j << k) & (all - 1));                    dp[nxt] += x;                    if (dp[nxt] >= MOD)                        dp[nxt] -= MOD;                }                if (Max - Min > 0)                    dp[j] = (dp[j] + 1LL * (Max - Min) * x) % MOD;            }        }        int ans = 0;        FF(i, 1 << sum, all)        {            ans += dp[i];            if (ans >= MOD)                ans -= MOD;        }        WI(ans);    }    return 0;}

转载地址:http://rgmcx.baihongyu.com/

你可能感兴趣的文章
mascara-1
查看>>
Jquery Form表单取值
查看>>
Android API level 与version对应关系
查看>>
Team Name
查看>>
String类
查看>>
西门子_TDC_数据耦合小经验
查看>>
[LeetCode] Copy List with Random Pointer
查看>>
openstack部署之nova
查看>>
JS组件系列——表格组件神器:bootstrap table
查看>>
存储过程Oracle(一)
查看>>
log4j日志归档
查看>>
mysql遇见error,1049
查看>>
codevs——2822 爱在心中
查看>>
Python基础班---第一部分(基础)---Python基础知识---认识Python
查看>>
JAVA MAC 配置
查看>>
1134 最长上升子序列 (序列型 DP)
查看>>
js冒泡排序
查看>>
第一次作业 4班卢炳武
查看>>
抽象类的调用
查看>>
使用硬盘,安装双系统,Win7+CentOS
查看>>