UVa 165. Stamps

Description

每張信封上面最多可以貼上h張郵票，請設計k種面額，並求出能組成的連續面額最大值。 例如當$h=3, k=2$，1和3元的面額最多可以連續從1組到7。

Input Format

輸入包含多筆測資
每組測資會給予$h$和$k$
當$h=k=0$時結束程式

Output Format

每組測試資料輸出一列，輸出k種面額，以及最大連續面額為多少。

Sample Input

3 2
0 0

Sample Output

  1  3 ->  7

UVa - 165

Solution

首先，可以先確認一定會有面額為1的郵票，因為畢竟是要組成連續的數字。
接著使用DFS求出第$2~k$的郵票面額。
在我的程式裡面，use[i]表第$i$郵票的值；maxsum[i]陣列表示第i郵票及之前所有郵票可以組到的連續面額最大值。
對於每一次遞迴，可確定當前第$i$個郵票枚舉的面額範圍必為use[i - 1] + 1 ~ maxsum[i - 1] + 1

優化筆記：

1. 在求maxsum[]的時候，有一種做法是DFS暴力搜尋所有組合，這裡使用DP+Bitwise的方法優化。
2. 在將use複製到ans時，用memcpy取代for，可以降低執行時間，優化結果如下圖。

Code

/*************************************************************************
  > File Name: 00165 - Stamps.cpp
  > Author: Samuel
  > Mail: enminghuang21119@gmail.com
  > Created Time: Fri Feb 16 16:53:08 2018
*************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int h, k, mx;
int use[10], maxsum[10], ans[10];
char check[75];
int bit;
void search(int index) {
    if (index == k) {
        if (maxsum[k - 1] > mx) {
            mx = maxsum[k - 1];
            memcpy(ans, use, sizeof(ans));
        }
        return;
    }
    for (int i = use[index - 1] + 1; i <= maxsum[index - 1] + 1; i++) {
        memset(check, 0, sizeof(check));
        check[0] = 1;
        use[index] = i;
        for (int j = 0; j <= index; j++)
            for (int k = use[j]; k < 75; k++)
                check[k] |= check[k - use[j]] << 1;
        int j = 0;
        while (check[++j] & bit);
        maxsum[index] = j - 1;
        search(index + 1);
    }
}
int main() {
    while (scanf("%d%d", &h, &k) && h + k) {
        memset(use, 0, sizeof(use));
        ans[0] = use[0] = 1;
        maxsum[0] = h;
        mx = 0;
        bit = 1;
        for (int i = 0; i < h; i++)
            bit |= bit << 1;
        search(1);
        for (int i = 0; i < k; i++)
            printf("%3d", ans[i]);
        printf(" ->%3d\n", mx);
    }
    return 0;
}