CFR 632 E. Thief in a Shop ( DP )

Problem - E - Codeforces

題意：
有 N 個價值的物品，每個都有無限多個。輸出拿恰好 K 個物品可以產生出的所有值。

資料規模：
The first line contains two integers n and k (1 ≤ n, k ≤ 1000) — the number of kinds of products and the number of products the thief will take.

解法：
FFT 可以搞，但太累了。
這用一個非常聰明的技巧就可以變成簡單 DP 問題。
主要的麻煩就是要拿恰好 K 個，但是：
把 A 裡最小的值稱作 X，接著將所有物品的價值減去 X。
那麼，只要用 K 個以下的物品湊出的價值，加上 K * X 就是原題可以湊出的值。
原因是，可以將最小那個值 ( 在新問題中是 0 )，任意的補，而之所以能這樣，也是因為一開始先給它扣掉去了。一開始聽也許會疑惑一下，可是等豁然開朗之後會發現真的很睿智。把恰好變成一個範圍，這樣的思想有時候是關鍵。

時間 / 空間複雜度：
O( N * K * MAXA )

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000;
const int MAXK = 1000;
const int MAXA = 1000;

int N, K;
int A[ MAXN ];
int dp[ MAXK * MAXA + 1 ];

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N >> K;
  for( int i = 0; i < N; ++i ){
    cin >> A[ i ];
  }
  sort( A, A + N );
  for( int i = 1; i < N; ++i ){
    A[ i ] -= A[ 0 ];
  }
  memset( dp, 0x3f3f3f3f, sizeof( dp ) );
  dp[ 0 ] = 0;
  for( int i = 1; i < N; ++i ){
    for( int j = 0; j + A[ i ] <= K * MAXA; ++j ){
      dp[ j + A[ i ] ] = min( dp[ j + A[ i ] ], dp[ j ] + 1 );
    }
  }
  for( int i = 0; i <= K * MAXA; ++i ){
    if( dp[ i ] <= K ){
      cout << i + A[ 0 ] * K << " ";
    }
  }
  return 0;
}