Codeforces Round #360 (Div. 1)C - The Values You Can Make

链接：http://codeforces.com/contest/687/problem/C

题意：给定n个数和一个k，对于每一个和为k的集合{a[1],a[2],...a[g]}都能凑成若个数。求所有的集合能凑出哪些数。

分析：我们设dp[i][j][k]表示前i个数在凑成j的数中能否凑出k，为0/1。那么状态直接转移即可。O(n^3)。

代码：

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<math.h>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int N=510;
const int MAX=1000000100;
const int mod=100000000;
const int MOD1=1000000007;
const int MOD2=1000000009;
const double EPS=0.00000001;
typedef long long ll;
const ll MOD=998244353;
const int INF=1000000010;
const double pi=acos(-1.0);
typedef double db;
typedef unsigned long long ull;
int a[N],dp[2][N][N];
int main()
{
    int i,j,h,n,k,now,old;
    scanf("%d%d", &n, &k);
    for (i=1;i<=n;i++) scanf("%d", &a[i]);
    memset(dp,0,sizeof(dp));
    dp[1][0][0]=1;now=old=1;
    for (i=1;i<=n;i++) {
        old=now;now^=1;
        for (j=0;j<=k;j++)
            for (h=0;h<=k;h++)
            if (dp[old][j][h]) {
                dp[now][j][h]=1;
                if (j+a[i]<=k&&h+a[i]<=k) {
                    dp[now][j+a[i]][h]=1;
                    dp[now][j+a[i]][h+a[i]]=1;
                }
            }
    }
    for (h=0,i=0;i<=k;i++)
    if (dp[now][k][i]) h++;
    printf("%d\n", h);
    for (i=0;i<=k;i++)
    if (dp[now][k][i]) printf("%d ", i);
    printf("\n");
    return 0;
}