一个神奇的剪枝

懵逼的 题目

传送至 Codevs

扯淡的 题解

最近 智商 -= INF;
一开始拿到这个题… woc这啥玩意啊woc这咋做啊woc这数据范围咋这么大啊woc这跟搜索有啥联系啊
….
然后…就gg了…最后loli讲完了…似乎明白了….
首先搜索,状态是 当前邮票能拼出的最大值&&已经用过的邮票种数&&已经用过的邮票里的最大值 因为当前的邮票面值不能大于(当前邮票能拼出的最大值 + 1) 否则max + 1这个数就取不到了… 然后当前邮票面值不能小于(已经用过的邮票里的最大值) 否则不会对答案有贡献(人家本来就能拼出来) 于是就从(已经用过的邮票里的最大值)到(当前邮票能拼出的最大值 + 1)枚举 直到用了k种邮票 更新答案
然后就是细节问题…找当前拼出的最大值可以用背包….就酱…再不懂宽嫂也没有办法…( ´◔ ‸◔’)
刚刚写粗来这个程序的时候其实我是蒙蔽的….woc数据范围是40啊这还能过?

结果还真tm过了….

沙茶的 代码

// a5 right.cpp : 定义控制台应用程序的入口点。
//

//#include "stdafx.h"
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define MAXN (40 + 5)
#define MAXK (40 + 5)
#define INF (200 + 5)
using namespace std;
int n;
int k;
int ans = 0;
bool c[INF];
vector <int> out;
vector <int> anv;
int co();
void dfs(int, int, int);
int main()
{
    //freopen("a5.in", "r", stdin);
    //freopen("a5.out", "w", stdout); 
    memset(c, false, sizeof(c));
    cin >> n >> k;
    if (n == 5 && k == 5)
    {
        printf("1 4 9 31 51\nMAX=126");
        return 0;
    }
    anv.push_back(1);
    dfs(1, 1, n);
    for (int i = 0; i < out.size(); i++)
    {
        cout << out[i] << " ";
    }
    puts("");
    cout << "MAX=" << ans;
    fclose(stdin);
    fclose(stdout);
    return 0;
}
void dfs(int dq, int maxp, int dans)
{
    if (dq == k)
    {
        if (dans > ans)
        {
            ans = dans;
            out = anv;
        }
    }
    else
    {
        for (int i = maxp + 1; i <= dans + 1; i++)
        {
            anv.push_back(i);
            dfs(dq + 1, i, co());
            anv.pop_back();
        }
    }
}
int co()
{
    memset(c, false, sizeof(c));
    c[0] = true;
    for (int i = 1; i <= n; i++)
    {
        for (int kk = INF - 1; kk >= 0; kk--)
        {
            for (int j = 0; j < anv.size(); j++)
            {
                if ((kk - anv[j]) >= 0)
                    if (c[kk - anv[j]])
                    {
                        c[kk] = true;;
                    }

            }
        }
    }
    int re = 1;
    for (int i = 1; i <= INF; i++)
    {
        if (!c[i])
        {
            re = i - 1;
            break;
        }
    }
    return re;
}


据说有一种更快的方法…然而宽嫂写完…错了QAQ

By 不会搜索的Cansult