HDU 5119 Happy Matt Friends（2014北京区域赛现场赛H题 裸背包DP）

时间：2021-01-27 16:05:15

虽然是一道还是算简单的DP，甚至不用滚动数组也能AC，数据量不算很大。

对于N个数，每个数只存在两个状态，取 和 不取。

容易得出状态转移方程：

dp[i][j] = dp[i - 1][j ^ a[i]] + dp[i - 1][j];

dp[i][j] 的意思是，对于数列 中前 i 个数字，使得 XOR 和恰好为 j 的方案数

状态转移方程中的 dp[i - 1][j] 即表示当前这个数字不取， dp[i - 1][j ^ a[i]] 表示当前这个数字要取。

这道题还是要好好理解阿！

source code :

//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler

#include <stdio.h>

#include <iostream>

#include <cstring>

#include <cmath>

#include <stack>

#include <queue>

#include <vector>

#include <algorithm>

#define ll long long

#define Max(a,b) (((a) > (b)) ? (a) : (b))

#define Min(a,b) (((a) < (b)) ? (a) : (b))

#define Abs(x) (((x) > 0) ? (x) : (-(x)))

using namespace std;

const int INF = 0x3f3f3f3f;

int dp[][ << ];

int a[];

int main(){

    int i, j, k, T, n, m, numCase = ;

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&n,&m);

        for(i = ; i <= n; ++i) scanf("%d", a + i);

        memset(dp, , sizeof(dp));

        dp[][] = ;

        for(i = ; i <= n; ++i){

            for(j = ; j < ( << ); ++j){

                dp[i % ][j] = dp[(i - ) % ][j ^ a[i]] + dp[(i - ) % ][j];

            }

        }

        long long ans = ;

        for(i = m; i < ( << ); ++i){

            ans += dp[n % ][i];

        }

        printf("Case #%d: %I64d\n",++numCase, ans);

    }

    return ;

}

相关文章