Our happy ending
- 题意:
输入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代表和为0(这样主要是转移方便,其实可以0表示和为0),第二个1表示和为1……
反思一下程序写的时候的问题:没有用滚动数组,导致错了很多次。由于这个题目的状态转移只会向更大的状态值(也可以是自己)转移,所以可以不采用滚动数组,一维解决。但是这样就需要额外注意一个问题,自己转移到自己的问题,由于这里理解的不是很好,导致一直查不出来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 + 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; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。