Codeforces 689 C The Values You Can Make(dp)

タイトル:
コインをいくつかあげて、サブセットの総価値とkを選んで、それから1つの選択したサブセットに対して、kを構成することができる以外に、選択したサブセットで他の価値を選ぶことができます.選択したすべてのサブセットにどれだけの価値が得られるかを聞いてみましょう.これに対してtagはダイナミックプランニングなので、上を考えますが、実行可能な状態が見つかりません.問題解を見てやっと分かった.機知に富んだ状態だ.dp[i][j][k]は、前のi個の硬貨がjのサブセットを構成し、中にkサイズの額面が得られる場合があるかどうかを示す.では、1つの硬貨について、全部で3つの移転があります.1、この硬貨は避難して選ばれた子が集中しています.2、この硬貨は、選択されたサブセットにあるが、出されていないサブセット、すなわちサブセットのサブセットである.3、このコインはすべての集合の中にあります.したがって、dp[i][j][k]=dp[i−1][j][k]‖dp[i−1][j−c[i][k]‖dp[i−−1][j−c[i]][k−c[i]]となる.これを得た後、可能な値が存在するかどうかを試してみることができます.コードを具体的に見る.
コード:

//
//  Created by  CQU_CST_WuErli
//  Copyright (c) 2016 CQU_CST_WuErli. All rights reserved.
//
//#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define CLR(x) memset(x,0,sizeof(x))
#define OFF(x) memset(x,-1,sizeof(x))
#define MEM(x,a) memset((x),(a),sizeof(x))
#define BUG cout << "I am here" << endl
#define lookln(x) cout << #x << "=" << x << endl
#define SI(a) scanf("%d", &a)
#define SII(a,b) scanf("%d%d", &a, &b)
#define SIII(a,b,c) scanf("%d%d%d", &a, &b, &c)
const int INF_INT=0x3f3f3f3f;
const long long INF_LL=0x7f7f7f7f;
const int MOD=1e9+7;
const double eps=1e-10;
const double pi=acos(-1);
typedef long long  ll;
using namespace std;

int n, k;
int c[550];
int dp[2][555][555];

int main(int argc, char const *argv[]) {
#ifdef LOCAL
    freopen("C:\\Users\\john\\Desktop\\in.txt","r",stdin);
    // freopen("C:\\Users\\john\\Desktop\\out.txt","w",stdout);
#endif
    while (SII(n, k) == 2) {
        for (int i = 1; i <= n; i++)
            SI(c[i]);
        CLR(dp);
        dp[0][0][0] = 1;
        for (int i = 1; i <= n; i++) {
            int now = i % 2;
            int last = now ^ 1;
            for (int j = 0; j <= k; j++) {
                for (int s = 0; s <= j; s++) {
                    dp[now][j][s] |= dp[last][j][s];
                    if (j >= c[i]) dp[now][j][s] |= dp[last][j - c[i]][s];
                    if (s >= c[i]) dp[now][j][s] |= dp[last][j - c[i]][s - c[i]];
                }
            }
        }
        vector<int> ans;
        for (int i = 0; i <= k; i++)
            if (dp[n % 2][k][i]) ans.push_back(i);
        cout << (int)ans.size() << endl;
        for (int i = 0; i < ans.size(); i++)
            cout << ans[i] << ' ';
        cout << endl;
    }
    return 0;
}
/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \|     |//  `.
            /  \|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\__/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                          BUG
*/