Our happy ending

时间：2014-08-04 21:41:58 收藏：0 阅读：526

题意：
输入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;
}

Our happy ending,布布扣,bubuko.com

原文：http://blog.csdn.net/wty__/article/details/38373441