上司のおごり

パソコン甲子園2009予選 問題08 上司のおごり

問題はこちら。

典型的な動的計画法の問題です。

K[i] を i 番目の金額、
Tⁱ[j] を i 番目までの金額を使って j を払えるかのフラグとする （1の場合に払えるものとする）と、

T⁰[j] を 0 で初期化し、
Tⁱ[j] = T^i-1[j] | T^i-1[j - K[i]]

となります。

あとは、i が素数で T[i] が 1 である i の最大値を求めます。

#include<iostream>
using namespace std;
#define KMAX 30
#define VMAX 1000000

int K[KMAX], T[VMAX+1];

void eratos ( int n, bool prime[]){
    for ( int i = 0; i <= n; i++ ) prime[i] = false;
    for ( int i = 3; i <= n; i += 2 ) prime[i] = true;
    prime[2] = true;
    for ( int i = 3; i*i <= n; i += 2 ){
        if ( !prime[i] ) continue;
        for ( int j = i + i; j <= n; j += i ) prime[j] = false;
    }
}

main(){
    bool prime[VMAX + 1];
    eratos( VMAX, prime );

    int k, v;
    while( cin >> k >> v && k && v ){
        for ( int i = 0; i < k; i++ ) cin >> K[i];
	
        for ( int j = 0; j <= v; j++ ) T[j] = 0;
        for ( int j = K[0]; j <= v; j += K[0] ) T[j] = 1;
        T[0] = 1;
        for ( int i = 1; i < k; i++ ){
            for ( int j = K[i]; j <= v; j++ ){
                T[j] = (T[j] | T[j-K[i]]);
            }
        }
        int ans = -1;
        for ( int i = v; i >= 2; i-- ){
            if ( prime[i] && T[i] ) { ans = i; break; }
        }
	
        if ( ans == -1 ) cout << "NA" << endl;
        else cout << ans << endl;
    }
}